Here is an $O(nm \log nm)$ solution, where $n,m$ are the dimensions of the matrix. Later we improve it to an optimal $O(nm)$ solution.
Let $A[i_1j_1],\ldots,A[i_{nm}j_{nm}]$ be the entries of $A$ in non-decreasing order; the indices $i_tj_t$ can be computed in time $O(nm\log nm)$. We will compute a new matrix $B$ with the same dimensions such that $B[ij]$ is the length of the longest increasing part ending at $A[ij]$. We compute the entries of $B$ in the order $B[i_1j_1],\ldots,B[i_{nm}j_{nm}]$, using the formula
$$
B[ij] =
1 + \max_{\substack{i'j' \sim ij \\ A[i'j'] < A[ij]}} B[i'j'],
$$
where $i'j' \sim ij$ means that $A[i'j']$ is a neighbor of $A[ij]$, and we set $B[ij] = 1$ if the maximum is over the empty set.
The answer is simply the maximum entry of $B$. You can find an actual longest increasing sequence by starting with a maximum entry of $B$, say equal to $\ell$, finding a neighbor equal to $\ell-1$, then a neighbor equal to $\ell-2$, and so on until hitting a neighbor equal to $1$. This gives you a longest increasing sequence in reverse order.
As an example, consider your matrix
$$
A = \begin{pmatrix}
1&2&3&4\\2&2&3&4\\3&2&3&4\\4&5&6&7
\end{pmatrix}.
$$
We can order the entries as follows (there are many possible orders, since the entries are not distinct):
$$
A[1,1],A[1,2],A[2,1],A[2,2],A[3,2],A[1,3],A[2,3],A[3,1],\\A[3,3],A[1,4],A[2,4],A[3,4],A[4,1],A[4,2],A[4,3],A[4,4].
$$
We now compute $B$ in the same order:
$$
\begin{pmatrix}
1& & & \\
& & & \\
& & & \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2& & \\
& & & \\
& & & \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2& & \\
2& & & \\
& & & \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2& & \\
2&1& & \\
& & & \\
& & &
\end{pmatrix}, \\
\begin{pmatrix}
1&2& & \\
2&1& & \\
&1& & \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3& \\
2&1& & \\
&1& & \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3& \\
2&1&2& \\
&1& & \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3& \\
2&1&2& \\
3&1& & \\
& & &
\end{pmatrix}, \\
\begin{pmatrix}
1&2&3& \\
2&1&2& \\
3&1&3& \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2& \\
3&1&3& \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3& \\
& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
& & &
\end{pmatrix}, \\
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4& & &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4&5& &
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4&5&6&
\end{pmatrix},
\begin{pmatrix}
1&2&3&4\\
2&1&2&3\\
3&1&3&4\\
4&5&6&7
\end{pmatrix}.
$$
We conclude that the answer is $7$. Retracing our steps, we highlight the following path in $B$, which corresponds to the longest increasing sequence in $A$ (accidentally, having exactly the same values):
$$
\begin{pmatrix}
1& & & \\
2& & & \\
3& & & \\
4&5&6&7
\end{pmatrix}.
$$
We can implement essentially the same solution in time $O(nm)$ using DFS. We go over the entries of $B$ in some arbitrary order, attempting to use the same recurrence formula we had before:
$$
B[ij] =
1 + \max_{\substack{i'j' \sim ij \\ A[i'j'] < A[ij]}} B[i'j'].
$$
If we are trying to access an entry $B[i'j']$ which hasn't already been computed we compute it recursively. Conversely, once an entry $B[ij]$ has been computed, there is no need to compute it again.
This can be implemented using the following pseudocode:
compute-B-matrix:
initialize B to be empty
for 1 <= i <= n and 1 <= j <= m:
if B[i,j] is empty, call compute-entry(i,j)
compute-entry(i,j):
let S = { neighbors (i',j') of (i,j) such that A[i',j'] < A[i,j] }
if S is empty:
set B[i,j] = 1
if S is non-empty:
for every (i',j') in S:
if B[i',j'] is empty, call compute-entry(i',j')
set B[i,j] = 1 + max({ B[i',j'] : (i',j') in S })
This solution essentially amounts to computing a topological ordering of a digraph naturally associated with $A$. Details left to the reader.
