329

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& grid) {
        int m = grid.size(), n=grid[0].size();
        int inDegree[m+1][n+1];
        memset(inDegree, 0, sizeof inDegree);

        // Set inDegree of each vertex.
        int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                for(int k=0; k<4; k++){
                    int nextX=i+dir[k][0], nextY=j+dir[k][1];
                    if(nextX>=0 && nextX<m && nextY>=0 && nextY<n && grid[i][j]<grid[nextX][nextY])
                        inDegree[nextX][nextY]++;
                }

        // Topo sort using BFS.
        int level = 0;
        queue<pair<int,int>> q;
        for(int i=0; i<m; i++)
            for(int j=0; j<n; j++)
                if(!inDegree[i][j])
                    q.push({i,j});

        while(!q.empty()){
            level++;
            int sz = q.size();
            for(int i=0; i<sz; i++){
                auto p = q.front(); q.pop();
                int curX=p.first, curY=p.second;
                for(int j=0; j<4; j++){
                    int nextX=curX+dir[j][0], nextY=curY+dir[j][1];
                    if(nextX>=0 && nextX<m && nextY>=0 && nextY<n && grid[nextX][nextY]>grid[curX][curY]){
                        if(--inDegree[nextX][nextY] == 0)
                            q.push({nextX,nextY});
                    }
                }
            }
        }
        return level;
    }
};