Untitled
unknown
plain_text
a month ago
952 B
1
Indexable
Never
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; } };