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

class Solution {
    
public:
    
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int dfs(vector<vector<int> >& matrix, int i, int j, vector<vector<int>>& cnt)
    {
        if(cnt[i][j]>1)
        {
            return cnt[i][j]; // 已经访问过了
        }
        // cnt[i][j]++; // 不能连续时 值就是1
        int n = matrix.size(), m = matrix[0].size();
        
        // bool flag = false;
        // 4方向遍历
        int du[4] = {0, 0, -1, 1};
        int dv[4] = {-1, 1, 0, 0};
        for(int k=0; k<4; ++k)
        {
            int na = i + dv[k];
            int nb = j + du[k];
            if(na>=0 && na<n && nb>=0 && nb<m && matrix[i][j]<matrix[na][nb])// 满足可以继续
            {
                cnt[i][j] = max(cnt[i][j], dfs(matrix, na, nb, cnt)+1);//该cnt保存的是最大值，每个方向的后继路径
            }
        }

        return cnt[i][j];// 最终的最大值
        


    }
    int solve(vector<vector<int> >& matrix) {
        // write code here
        int n = matrix.size(), m = matrix[0].size();

        if(n==0 || m==0)
        {
            return 0;
        }

        vector<vector<int>> cnt(n, vector<int>(m, 1)); // 存储每个位置为起点的最长路径
        int l=0;
        // 遍历每个起点
        for(int i=0; i<n; ++i)
        {
            for(int j=0; j<m; ++j)
            {
                
                l = max(dfs(matrix, i, j, cnt), l); // 更新当前最大值

                
            }
        }

        
        return l;
    }
};

O(mn) O(mn) 参考官解写了一遍

和BM 57岛屿数量要一块连！