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

class Solution {
public:
    bool check(int x,int y,vector<vector<int>>&matrix,vector<vector<bool>>&f)
    {
        return x>=0&&x<matrix.size()&&y>=0&&y<matrix[0].size()&&!f[x][y];
    }
    void dfs(int x,int y,vector<vector<int>>&matrix,vector<vector<bool>>&f,vector<vector<int>>&dp)
    {
        if(dp[x][y])return;
        vector<vector<int>>dir{{1,0},{0,1},{-1,0},{0,-1}};
        for(auto m:dir)
        {
            int xx=m[0]+x,yy=m[1]+y;
            if(check(xx,yy,matrix,f)&&matrix[xx][yy]>matrix[x][y])
            {
                f[xx][yy]=true;
                dfs(xx,yy,matrix,f,dp);
                f[xx][yy]=false;
                if(dp[x][y]<dp[xx][yy]+1)dp[x][y]=dp[xx][yy]+1;
            }
        }
        if(!dp[x][y])dp[x][y]=1;
    }
    int solve(vector<vector<int> >& matrix) {
        vector<vector<bool>>f(matrix.size()+10,vector<bool>(matrix[0].size()+10,false));
        vector<vector<int>>dp(matrix.size()+10,vector<int>(matrix[0].size()+10,0));
        int ma=0xc0c0c0c0,res=0;
        for(int i=0;i<matrix.size();i++)
        for(int j=0;j<matrix[0].size();j++)
        {
            if(dp[i][j])continue;
            dfs(i,j,matrix,f,dp);
            ma=max(ma,dp[i][j]);
        }
        return ma;
    }
};