[RainbowSecret] clean C++ implementation with detailed explanation

• At first, I use the bool-flag-array to record whether the position (i,j) has been visited. But when visited before, I should return the recorded value. When not, I should calculate the 4-direction-value and set the max value to be the value and add 1 to get the result.

Also, we can update the max-value when DFS .

``````class Solution {
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
int result=INT_MIN;
int m=matrix.size();
if(m==0)  return 0;
int n=matrix[0].size();
vector<vector<int>> state(m, vector<int>(n, 0));
for(int i=0; i<m; i++){
for(int j=0; j<n; j++){
if(state[i][j]==0)
dfs(i,j,matrix,state,result);
}
}
return result;
}

/*** return the max-len-start-from-cur-position-i-j ***/
int dfs(int i, int j, vector<vector<int>>& matrix, vector<vector<int>>& state, int& result){
if(state[i][j]!=0)  return state[i][j];

int len1=0, len2=0, len3=0, len4=0;
/*** only-move-forward-when-next-step-value-satisfy-the-condition ***/
if(i+1<state.size()  &&  matrix[i+1][j]>matrix[i][j])
len1=dfs(i+1, j, matrix, state, result);
if(i-1>=0  &&  matrix[i-1][j]>matrix[i][j])
len2=dfs(i-1, j, matrix, state, result);
if(j+1<state[0].size()  &&  matrix[i][j+1]>matrix[i][j])
len3=dfs(i, j+1, matrix, state, result);
if(j-1>=0  &&  matrix[i][j-1]>matrix[i][j])
len4=dfs(i, j-1, matrix, state, result);
/*** get-the-max-value-start-from-i-j ***/
state[i][j] =  max(max(max(len1, len2), len3), len4);
state[i][j]++;
/*** update-the-final-value ***/
result=max(result, state[i][j]);
return state[i][j];
}
};``````

• In fact , the posted solution is really dirty .... Here is a much better coding style implementation ...

``````class Solution {
const vector<vector<int>> move = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
public:
int longestIncreasingPath(vector<vector<int>>& matrix) {
if(matrix.size()==0) return 0;
int m = matrix.size(), n = matrix[0].size();
vector<vector<int>> cache(m, vector<int>(n, 0));
int result = 1;
for(int i = 0; i < m; i++){
for(int j = 0; j < n; j++){
int len = dfs(matrix, i, j, m, n, cache);
result = max(result, len);
}
}
return result;
}

int dfs(vector<vector<int>>& matrix, int i, int j, int m, int n, vector<vector<int>>& cache){
if(cache[i][j] != 0)  return cache[i][j];
int result = 1;
for(auto dir : move) {
int x = i + dir[0], y = j + dir[1];
if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j])  continue;
int len = 1 + dfs(matrix, x, y, m, n, cache);
result = max(result, len);
}
cache[i][j] = result;
return result;
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.