Untitled

class Solution {
public:
    int dfs(int x,int y,vector<vector<int>>& m, vector<vector<int>>&dir,vector<vector<int>>&dp){
        if(dp[x][y]!=0) return dp[x][y];

        int mx=1;
        for(auto d:dir){
            int new_x=x+d[0];
            int new_y=y+d[1];
            if(0<=new_x && new_x<m.size() && 0<=new_y && new_y<m[0].size() && m[new_x][new_y]>m[x][y]){
                int l= 1+ dfs(new_x,new_y,m,dir,dp);
                mx=max(l,mx);
            }
        }
        return dp[x][y]=mx;
    }


    int longestIncreasingPath(vector<vector<int>>& m) {
        vector<vector<int>> dir = {{-1,0},{1,0},{0,-1},{0,1}}; // up,down,left,right
        vector<vector<int>>dp(m.size(),vector<int>(m[0].size(),0));
        int ans=1;
        for(int i=0;i<m.size();i++){
            for(int j=0;j<m[0].size();j++){
                ans=max(ans,dfs(i,j,m,dir,dp));
            }
        }
        return ans;
    }
};