题解 | 矩阵最长递增路径

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 递增路径的最大长度
     * @param matrix int整型vector<vector<>> 描述矩阵的每个数
     * @return int整型
     */
    int res=0;
    int solve(vector<vector<int> >& matrix) {
        // write code here
        int m=matrix.size();
        if(m==0) return 0;
        int n=matrix[0].size();
        for(int i=0;i<m;++i){
            for(int j=0;j<n;++j){
                res=max(res,dfs(matrix,i,j,-1));
            }
        }
        return res;
    }
    int dfs(vector<vector<int> >& matrix,int x,int y,int pre){
        if(x<0||y<0||x>=matrix.size()||y>=matrix.size()){
            return 0;
        }
        if(pre>=matrix[x][y]) return 0;
        int mx=0;
        mx = max(mx, dfs(matrix, x + 1, y,matrix[x][y]));
        mx = max(mx, dfs(matrix, x , y + 1,matrix[x][y]));
        mx = max(mx, dfs(matrix, x - 1, y,matrix[x][y]));
        mx = max(mx, dfs(matrix, x, y - 1,matrix[x][y]));
        return mx+1;
    }
};