417. 太平洋大西洋水流问题
DFS
逆向思维，水往高处流。这样只用对矩形四条边进行搜索。完成后遍历矩阵寻找重合部分，即为两个大洋向上流都能到达的位置。
class Solution { public: vector<int> direction{-1, 0, 1, 0, -1}; vector<vector<int>> pacificAtlantic(vector<vector<int>> &heights) { if (heights.empty() || heights[0].empty()) { return {}; } vector<vector<int>> ans; int m = heights.size(); int n = heights[0].size(); vector<vector<bool>> can_reach_p(m, vector<bool>(n, false)); vector<vector<bool>> can_reach_a(m, vector<bool>(n, false)); for (int i = 0; i < m; i++) { // 判定左右两边的水所能到达的范围 DFS(heights, can_reach_p, i, 0); DFS(heights, can_reach_a, i, n - 1); } for (int i = 0; i < n; i++) { // 判定上下两边的水所能到达的范围 DFS(heights, can_reach_p, 0, i); DFS(heights, can_reach_a, m - 1, i); } for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (can_reach_p[i][j] && can_reach_a[i][j]) { ans.push_back(vector<int>{i, j}); } } } return ans; } void DFS(vector<vector<int>> &heights, vector<vector<bool>> &visited, int a, int b) { visited[a][b] = true; int m = heights.size(); int n = heights[0].size(); for (int i = 0; i < 4; i++) { int x = a + direction[i]; int y = b + direction[i + 1]; if (x >= 0 && x < m && y >= 0 && y < n && !visited[x][y] && heights[a][b] <= heights[x][y]) { DFS(heights, visited, x, y); } } } };
