417. Pacific Atlantic Water Flow

We should start from the boundary of the matrix to see if they can reach the other ocean. So it is a typical DSF problem. For DSF problem, we need to have a visited matrix. The trick here is right on the visited matrix. The value in visited matrix is no long bool now. It should use bit to represent the ocean. We can have 0b01 to be pacific and 0b10 to be atlantic. So only when visited becomes 0b11, we know the element is able to reach both oceans.

1:  class Solution {  
2:  private:  
3:    int rows, cols;  
4:    vector<pair<int,int>> res;  
5:    vector<vector<int>> visited;  
6:    vector<pair<int,int>> dir = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};  
7:  public:  
8:    vector<pair<int, int>> pacificAtlantic(vector<vector<int>>& matrix) {  
9:      if (matrix.empty()) return res;  
10:      rows = matrix.size(), cols = matrix[0].size();  
11:      visited = vector<vector<int>>(rows, vector<int>(cols, 0));  
12:      for (int i = 0; i < rows; i++) {  
13:        dfs(matrix, i, 0, INT_MIN, 1); // 1 is pacific  
14:        dfs(matrix, i, cols-1, INT_MIN, 2); // 2 is atlatic  
15:      }  
16:      for (int j = 0; j < cols; j++) {  
17:        dfs(matrix, 0, j, INT_MIN, 1);  
18:        dfs(matrix, rows-1, j, INT_MIN, 2);  
19:      }  
20:      return res;  
21:    }  
22:    void dfs(vector<vector<int>> &matrix, int i, int j, int prev, int ocean) {  
23:      if (i<0||j<0||i==rows||j==cols||matrix[i][j]<prev||(visited[i][j]&ocean)==ocean) return;  
24:      visited[i][j] |= ocean;  
25:      if (visited[i][j] == 3) res.push_back(make_pair(i, j));  
26:      for (int d = 0; d < dir.size(); d++) {  
27:        int ii = i + dir[d].first;  
28:        int jj = j + dir[d].second;  
29:        dfs(matrix, ii, jj, matrix[i][j], visited[i][j]);  
30:      }  
31:    }  
32:  };