Finding the length of the longest increasing path in a matrix
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'] &lt; 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&amp;2&amp;3&amp;4\\2&amp;2&amp;3&amp;4\\3&amp;2&amp;3&amp;4\\4&amp;5&amp;6&amp;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&amp; &amp; &amp; \\
 &amp; &amp; &amp; \\
 &amp; &amp; &amp; \\
 &amp; &amp; &amp;
\end{pmatrix},
\begin{pmatrix}
1&amp;2&amp; &amp; \\
 &amp; &amp; &amp; \\
 &amp; &amp; &amp; \\
 &amp; &amp; &amp;
\end{pmatrix},
\begin{pmatrix}
1&amp;2&amp; &amp; \\
2&amp; &amp; &amp; \\
 &amp; &amp; &amp; \\
 &amp; &amp; &amp;
\end{pmatrix},
\begin{pmatrix}
1&amp;2&amp; &amp; \\
2&amp;1&amp; &amp; \\
 &amp; &amp; &amp; \\
 &amp; &amp; &amp;
\end{pmatrix}, \\
\begin{pmatrix}
1&amp;2&amp; &amp; \\
2&amp;1&amp; &amp; \\
 &amp;1&amp; &amp; \\
 &amp; &amp; &amp;
\end{pmatrix},
\begin{pmatrix}
1&amp;2&amp;3&amp; \\
2&amp;1&amp; &amp; \\
 &amp;1&amp; &amp; \\
 &amp; &amp; &amp;
\end{pmatrix},
\begin{pmatrix}
1&amp;2&amp;3&amp; \\
2&amp;1&amp;2&amp; \\
 &amp;1&amp; &amp; \\
 &amp; &amp; &amp;
\end{pmatrix},
\begin{pmatrix}
1&amp;2&amp;3&amp; \\
2&amp;1&amp;2&amp; \\
3&amp;1&amp; &amp; \\
 &amp; &amp; &amp;
\end{pmatrix}, \\
\begin{pmatrix}
1&amp;2&amp;3&amp; \\
2&amp;1&amp;2&amp; \\
3&amp;1&amp;3&amp; \\
 &amp; &amp; &amp;
\end{pmatrix},
\begin{pmatrix}
1&amp;2&amp;3&amp;4\\
2&amp;1&amp;2&amp; \\
3&amp;1&amp;3&amp; \\
 &amp; &amp; &amp;
\end{pmatrix},
\begin{pmatrix}
1&amp;2&amp;3&amp;4\\
2&amp;1&amp;2&amp;3\\
3&amp;1&amp;3&amp; \\
 &amp; &amp; &amp;
\end{pmatrix},
\begin{pmatrix}
1&amp;2&amp;3&amp;4\\
2&amp;1&amp;2&amp;3\\
3&amp;1&amp;3&amp;4\\
 &amp; &amp; &amp;
\end{pmatrix}, \\
\begin{pmatrix}
1&amp;2&amp;3&amp;4\\
2&amp;1&amp;2&amp;3\\
3&amp;1&amp;3&amp;4\\
4&amp; &amp; &amp;
\end{pmatrix},
\begin{pmatrix}
1&amp;2&amp;3&amp;4\\
2&amp;1&amp;2&amp;3\\
3&amp;1&amp;3&amp;4\\
4&amp;5&amp; &amp;
\end{pmatrix},
\begin{pmatrix}
1&amp;2&amp;3&amp;4\\
2&amp;1&amp;2&amp;3\\
3&amp;1&amp;3&amp;4\\
4&amp;5&amp;6&amp;
\end{pmatrix},
\begin{pmatrix}
1&amp;2&amp;3&amp;4\\
2&amp;1&amp;2&amp;3\\
3&amp;1&amp;3&amp;4\\
4&amp;5&amp;6&amp;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&amp; &amp; &amp; \\
2&amp; &amp; &amp; \\
3&amp; &amp; &amp; \\
4&amp;5&amp;6&amp;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'] &lt; 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 &lt;= i &lt;= n and 1 &lt;= j &lt;= 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'] &lt; 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.