LeetCode 329. 矩阵中的最长递增路径

记忆化深搜，用unordered_map记录是否搜过，当前的最优值是什么；

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        unordered_map<int, int>ump;
        int m=matrix.size();
        int n=matrix[0].size();
        int ret=0;
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++){
                if(!ump.count(i*n+j)){
                    dfs(matrix,ump,i,j,m,n);
                }
                ret=max(ret,ump[i*n+j]);
            }
        }
        return ret;
    }

    int dfs(vector<vector<int>>& matrix,unordered_map<int, int>& ump,int x,int y,int m,int n){
        if(ump.count(n*x+y)){
            //如果该节点已经探索过；
            return ump[n*x+y];
        }
        //如果还没有探索过；
        int maxn=0;
        for(int i=0;i<dir.size();i++){
            int nx=x+dir[i][0];
            int ny=y+dir[i][1];
            if(nx>=0&&ny>=0&&nx<m&&ny<n&&matrix[nx][ny]>matrix[x][y]){
                int ret=dfs(matrix,ump,nx,ny,m,n);
                maxn=max(ret,maxn);
            }
        }
        ump[n*x+y]=maxn+1;
        return ump[n*x+y];
    }

    vector<vector<int>>dir={{0,1},{1,0},{-1,0},{0,-1}};
};