Untitled

mail@pastecode.io avatar
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;
    }
};