# C++ DFS solution

• #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));
}
}
}
}
};

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