LeetCode 329. Longest Increasing Path in a Matrix(DFS，记忆化搜索)

题目

题解：DFS，同时记住已经DFS的结果，防止重复搜索

class Solution {
public:
    vector<vector<int>> vis;
    int dir[4][2] = {{0,1},{0,-1},{1,0},{-1,0}};
    int n,m;
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        n=matrix.size();
        if(n==0)
            return 0;
        m=matrix[0].size();
        
        vis=matrix;
        
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                vis[i][j]=-1;
            }
        }
        int ans=0;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(vis[i][j]==-1)
                    vis[i][j]=dfs(i,j,matrix);
                
                ans=max(ans,vis[i][j]);
            }
        }
        
        return ans;
    }
    
    int dfs(int x,int y,vector<vector<int>>& matrix)
    {
        if(vis[x][y]!=-1)
            return vis[x][y];
        int res=1;
        for(int i=0;i<4;i++)
        {
            int xx = x+dir[i][0];
            int yy = y+dir[i][1];
            if(xx<0||xx>=n||yy<0||yy>=m)
                continue;
            if(matrix[xx][yy]<matrix[x][y])
            {
               vis[xx][yy] = dfs(xx,yy,matrix);
               res=max(res,1+vis[xx][yy]);
            }
        }
        return res;
    }
};