题解 | #矩阵最长递增路径#

class Solution {
public:
    //记录四个方向
    int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int n, m;
    //深度优先搜索，返回最大单元格数
    int dfs(vector<vector<int> > &matrix, vector<vector<int> > &dp, int i, int j) {
        if(dp[i][j] != 0)
            return dp[i][j];
        dp[i][j]++;
        for(int k = 0; k < 4; k++){
            int nexti = i + dirs[k][0];
            int nextj = j + dirs[k][1];
            //判断条件
            if (nexti >= 0 && nexti < n && nextj >= 0 && nextj < m && matrix[nexti][nextj] > matrix[i][j]) 
                dp[i][j] = max(dp[i][j], dfs(matrix, dp, nexti, nextj) + 1);
        }
        return dp[i][j];
    }
    int solve(vector<vector<int> >& matrix) {
        //矩阵不为空
        if(matrix.size() == 0 || matrix[0].size() == 0) 
            return 0;
        int res = 0;
        n = matrix.size();
        m = matrix[0].size();
        //i，j处的单元格拥有的最长递增路径
        vector<vector<int> > dp (n, vector <int> (m));  
        for(int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                //更新最大值
                res = max(res, dfs(matrix, dp, i, j)); 
        return res;
    }
};


// #include <vector>
// class Solution {
// public:
//     /**
//      * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
//      *
//      * 递增路径的最大长度
//      * @param matrix int整型vector<vector<>> 描述矩阵的每个数
//      * @return int整型
//      */
//     int ans=0;

//     void dfs(vector<vector<int> >& matrix, vector<vector<int> > flag, int len, int i, int j)
//     {
//         int n=matrix.size();
//         int m=matrix[i].size();

//         flag[i][j] = 1;
//         // 回溯的条件是什么呢？
//         // 条件为：该点没有其它位置可走了
//         if((i-1<0 || flag[i-1][j] || matrix[i-1][j]<matrix[i][j]) && (i+1>=n || flag[i+1][j] || matrix[i+1][j]<matrix[i][j]) && (j-1<0 || flag[i][j-1] || matrix[i][j-1]<matrix[i][j]) && (j+1>=m || flag[i][j+1] || matrix[i][j+1]<matrix[i][j]))
//         {
//             ans = max(ans,len);
//             return;
//         }        

//         if(i-1>=0 && matrix[i-1][j]>matrix[i][j] && !flag[i-1][j])
//             dfs(matrix, flag, len+1, i-1, j);

//         if(i+1<n && matrix[i+1][j]>matrix[i][j] && !flag[i+1][j])
//             dfs(matrix, flag, len+1, i+1, j);

//         if(j-1>=0 && matrix[i][j-1]>matrix[i][j] && !flag[i][j-1])
//             dfs(matrix, flag, len+1, i, j-1);

//         if(j+1<m && matrix[i][j+1]>matrix[i][j] && !flag[i][j+1])
//             dfs(matrix, flag, len+1, i, j+1);
           
//     }

//     int solve(vector<vector<int> >& matrix) {
//         // write code here
//         int row=matrix.size();
//         int col=matrix[0].size();
//         // 判断位置是否已经遍历过
//         vector<vector<int> > flag(row,vector<int>(col,0));
//         for(int i=0; i<row; ++i)
//         {
//             for(int j=0; j<col; ++j)
//             {
//                 dfs(matrix,flag,1,i,j);
//             }
                
//         }

//         return ans;
//     }
// };