Untitled
unknown
plain_text
a month ago
1.6 kB
1
Indexable
Never
class Solution { //TOPOLOGICAL,BFS public: int longestIncreasingPath(vector<vector<int>>& m) { vector<vector<int>> dir= {{1,0},{-1,0},{0,-1},{0,1}}; vector<vector<int>> indegree(m.size(),vector<int>(m[0].size(),0)); for(int x=0;x<m.size();x++){//indegree for(int y=0;y<m[0].size();y++){ for(auto d:dir){ int new_x=x+d[0], new_y=y+d[1]; if(new_x>=0 && new_x<m.size() && new_y>=0 && new_y<m[0].size() && m[new_x][new_y]<m[x][y]) indegree[x][y]++; } } } queue<pair<int,int>>q; for(int x=0;x<m.size();x++){ // initialising queue for(int y=0;y<m[0].size();y++){ if(indegree[x][y]==0) q.push({x,y}); } } int len=0; while(!q.empty()){ //topo starts int s=q.size(); while(s--){ pair<int,int>p=q.front(); q.pop(); int x=p.first, y=p.second; for(auto d:dir){ int new_x=x+d[0], 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]){//edg s prsnt if[new_x][new_y]>m[x][y] indegree[new_x][new_y]--; if(indegree[new_x][new_y]==0) q.push({new_x,new_y}); } } } len++; } return len; } };