# 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;
}
};```