太平洋大西洋水流问题
难度：中等
反向思维，反过来从海域到格子则是按照从低到高规则进行，同时本身处于边缘的格子与海域联通。因此我们可以使用两遍BFS 进行求解：分别从与当前海域直接相连的边缘格子出发，统计能够流向当前海域的格子集合，两片海域求得的集合交集即是答案。
代码如下：
public class PacificAtlanticWaterFlow {
int m;
int n;
int[][] g;
int[][] dirs = new int[][]{{1,0},{-1,0},{0,1},{0,-1}};
public List<List<Integer>> pacificAtlantic(int[][] heights) {
g = heights;
m = g.length;
n = g[0].length;
Deque<int[]> deque1 = new ArrayDeque();
Deque<int[]> deque2 = new ArrayDeque();
boolean[][] res1 = new boolean[m][n];
boolean[][] res2 = new boolean[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0){
res1[i][j] = true;
deque1.addLast(new int[]{i,j});
}
if (i == m-1 || j == n-1){
res2[i][j] = true;
deque2.addLast(new int[]{i,j});
}
}
}
bfs(deque1,res1);
bfs(deque2,res2);
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (res1[i][j] && res2[i][j]) {
List<Integer> list = new ArrayList<>();
list.add(i); list.add(j);
ans.add(list);
}
}
}
return ans;
}
void bfs(Deque<int[]> d, boolean[][] res) {
while (!d.isEmpty()) {
int[] info = d.pollFirst();
int x = info[0], y = info[1], t = g[x][y];
for (int[] di : dirs) {
int nx = x + di[0], ny = y + di[1];
if (nx < 0 || nx >= m || ny < 0 || ny >= n) continue;
if (res[nx][ny] || g[nx][ny] < t) continue;
d.addLast(new int[]{nx, ny});
res[nx][ny] = true;
}
}
}
}
