The question is just a 2 dimensional version of LIS. We can use brute force, but it is too costful. By storing the longest number of increasing subsequence starting from the node (i,j) in a 2d array, we can effectively prune many redundant recursive computations (although it's a dfs).

```
int longestpath(vector<vector<int>>& matrix, vector<vector<int>>& states, int i, int j, int m, int n) {
if(states[i][j] > 0)
return states[i][j];
int maxd = 0;
if(j>0 && matrix[i][j-1] < matrix[i][j]) {
int left = longestpath(matrix, states, i, j-1, m, n);
maxd = max(maxd, left);
}
if(j<n-1 && matrix[i][j+1] < matrix[i][j]) {
int right = longestpath(matrix, states, i, j+1, m, n);
maxd = max(maxd, right);
};
if(i>0 && matrix[i-1][j] < matrix[i][j]) {
int up = longestpath(matrix, states, i-1, j, m, n);
maxd = max(maxd, up);
};
if(i<m-1 && matrix[i+1][j] < matrix[i][j]) {
int down = longestpath(matrix, states, i+1, j, m, n);
maxd = max(maxd, down);
};
states[i][j] = maxd + 1;
return states[i][j];
}
int longestIncreasingPath(vector<vector<int>>& matrix) {
int m = matrix.size();
if (m == 0) return 0;
int n = matrix[0].size();
int res = 0;
vector<vector<int>> states(m, vector<int>(n, 0));
for(int i = 0; i < m; ++ i) {
for(int j = 0; j < n; ++ j) {
//each element
res = max(res, longestpath(matrix, states, i, j, m, n));
}
}
return res;
}
```