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

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

完完整整自己写的，DFS太奇妙了