C++ DFS solution


  • 0
    V
    #define INIT 0
    #define IN_PROGRESS 1
    #define CANNOT_FLOW 2
    #define CAN_FLOW 3
    
    
    class Solution {
    public:
        vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {
            vector<pair<int, int>> grid;
            int m = matrix.size();
            if(m == 0) {
                return grid;
            }
            int n = matrix[0].size();
            vector<vector<int>> pacific(m, vector<int>(n, INIT));
            vector<vector<int>> atlantic(m, vector<int>(n, INIT));
            fillPacific(pacific, matrix, m, n);
            fillAtlantic(atlantic, matrix, m, n);
            fillGridCoord(grid, pacific, atlantic);
            return(grid);
        }
        
        void fillPacific(vector<vector<int>> &pacific, vector<vector<int>>& matrix, int nR, int nC) {
            for(int i=0; i<nR; i++) {
                pacific[i][0] = CAN_FLOW; 
            }
            for(int i=0; i<nC; i++) {
                pacific[0][i] = CAN_FLOW; 
            }
            for(int i=1; i<nR; i++) {
                for(int j=1; j<nC; j++) {
                    if(pacific[i][j] != CAN_FLOW) {
                        dfs(i, j, nR, nC, pacific, matrix);
                    }
                }
            }
        }
        
        void fillAtlantic(vector<vector<int>> &atlantic, vector<vector<int>>& matrix, int nR, int nC) {
            for(int i=nR-1; i>=0; i--) {
                atlantic[i][nC-1] = CAN_FLOW; 
            }
            for(int i=nC-1; i>=0; i--) {
                atlantic[nR-1][i] = CAN_FLOW; 
            }
            for(int i=nR-2; i>=0; i--) {
                for(int j=nC-2; j>=0; j--) {
                    if(atlantic[i][j] != CAN_FLOW) {
                        dfs(i, j, nR, nC, atlantic, matrix);
                    }
                }
            }
        }
        
        int dfs(int rPos, int cPos, int nR, int nC, vector<vector<int>> &pacificAtlantic, vector<vector<int>>& matrix) {
            if(rPos < 0 || cPos < 0 || rPos >= nR || cPos >= nC) {
                return CANNOT_FLOW;
            }
            if(pacificAtlantic[rPos][cPos] == CANNOT_FLOW || pacificAtlantic[rPos][cPos] == IN_PROGRESS) {
                return CANNOT_FLOW;
            }
            if(pacificAtlantic[rPos][cPos] == CAN_FLOW) {
                return CAN_FLOW;
            }
            pacificAtlantic[rPos][cPos] = IN_PROGRESS;
            int waterFlow = CANNOT_FLOW;
            if(cPos < nC-1 && matrix[rPos][cPos+1] <= matrix[rPos][cPos]) {
                waterFlow |= dfs(rPos, cPos+1, nR, nC, pacificAtlantic, matrix);
            }
            if(cPos > 0 && matrix[rPos][cPos-1] <= matrix[rPos][cPos]) {
                waterFlow |= dfs(rPos, cPos-1, nR, nC, pacificAtlantic, matrix);
            }
            if(rPos < nR-1 && matrix[rPos+1][cPos] <= matrix[rPos][cPos]) {
                waterFlow |= dfs(rPos+1, cPos, nR, nC, pacificAtlantic, matrix);
            }
            if(rPos > 0 && matrix[rPos-1][cPos] <= matrix[rPos][cPos]) {
                waterFlow |= dfs(rPos-1, cPos, nR, nC, pacificAtlantic, matrix);
            }
            if(waterFlow == CANNOT_FLOW) {
                pacificAtlantic[rPos][cPos] = INIT;
            } else {
                pacificAtlantic[rPos][cPos] = CAN_FLOW;
            }
            return(waterFlow);
        }
        
        void fillGridCoord(vector<pair<int, int>> &grid, vector<vector<int>> &pacific, vector<vector<int>> &atlantic) {
            for(int i=0; i<pacific.size(); i++) {
                for(int j=0; j<pacific[0].size(); j++) {
                    if(pacific[i][j] == CAN_FLOW && atlantic[i][j] == CAN_FLOW) {
                        grid.push_back(make_pair(i,j));
                    }
                }
            }
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.