LeetCode 417 - Pacific Atlantic Water Flow

作者 QIFAN 日期 2017-01-28
LeetCode 417 - Pacific Atlantic Water Flow

原题链接: 417. Pacific Atlantic Water Flow


题干

给定一个二维数组,代表海水的海拔,左边边和上边边连着太平洋,右边边和下边边连着亚特兰洋,海水可以上下左右四个方向流动,但是只能流向海拔相等或者海拔更低处,要求返回所有既能流到太平洋也能流到亚特兰大洋的点。

思路

DFS

常规做法是将可以流到太平洋与可以流到亚特兰大洋的点分别做一个集合,然后求交集。

本文用 boolean[][] 来存储,先使用 DFS 遍历所有的点,若有点的海拔比其他方向的高,若该点可以流到 (row, col) == true ,则对周围四个方向进行 DFS ,如果不能,则直接返回。我这里用了两个矩阵表示状态,可以合成一个做。

之前还犯了一个错误就是进行了 $O(MN)$ 的遍历,其实只要 $O(M+N)$ ,因为所有的开始都是从四条边。

代码:

public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> res = new ArrayList<>();
if(matrix.length == 0) {
return res;
}
int M = matrix.length;
int N = matrix[0].length;
boolean[][] pacific = new boolean[M][N];
boolean[][] atlantic = new boolean[M][N];
for (int i = 0; i < M; i++) {
if (i == 0) {
Arrays.fill(pacific[i], true); // top line
}
if (i == M - 1) {
Arrays.fill(atlantic[i], true); // bottom line
}
pacific[i][0] = true; // left line
atlantic[i][N - 1] = true; // right line
}
for (int row = 0; row < M; row++) {
DFS(row, 0, matrix, pacific);
DFS(M - 1 - row, N - 1, matrix, atlantic);
}
for (int col = 0; col < N; col++) {
DFS(0, col, matrix, pacific);
DFS(M - 1, N - 1 - col, matrix, atlantic);
}
for (int row = 0; row < M; row++) {
for (int col = 0; col < N; col++) {
if (pacific[row][col] && atlantic[row][col]) {
res.add(new int[]{row, col});
}
}
}
return res;
}
private void DFS(int row, int col, int[][] matrix, boolean[][] ocean) {
if (row < 0 || row > matrix.length - 1 || col < 0 || col > matrix[0].length - 1 || !ocean[row][col]) {
return;
}
if (row < matrix.length - 1 && !ocean[row + 1][col] && matrix[row][col] <= matrix[row + 1][col]) {
ocean[row + 1][col] = true;
DFS(row + 1, col, matrix, ocean);
}
if (col < matrix[0].length - 1 && !ocean[row][col + 1] && matrix[row][col] <= matrix[row][col + 1]) {
ocean[row][col + 1] = true;
DFS(row, col + 1, matrix, ocean);
}
if (row > 0 && !ocean[row - 1][col] && matrix[row][col] <= matrix[row - 1][col]) {
ocean[row - 1][col] = true;
DFS(row - 1, col, matrix, ocean);
}
if (col > 0 && !ocean[row][col - 1] && matrix[row][col] <= matrix[row][col - 1]) {
ocean[row][col - 1] = true;
DFS(row, col - 1, matrix, ocean);
}
}

BFS

BFS 的还需要一个数据结构来保存一轮新加入的点,本文使用 Queue 。
然后学习了一个方向的表示,用一个数组 dir 存储 (0,1),(1,0),(0,-1),(-1,0) ,这样就可以直接用 (row + dir[i][0], col + dir[i][1]) 表示延展的点,代码可以干净很多。

因为用了额外的 queue ,时间和空间成本都增大了。

参考:https://discuss.leetcode.com/topic/62379/java-bfs-dfs-from-ocean

代码:

int[][] dir = {{0,1},{1,0},{0,-1},{-1,0}};
public List<int[]> pacificAtlantic(int[][] matrix) {
List<int[]> res = new ArrayList<>();
if (matrix == null || matrix.length == 0) {
return res;
}
int M = matrix.length;
int N = matrix[0].length;
boolean[][] pacific = new boolean[M][N];
boolean[][] atlantic = new boolean[M][N];
Queue<int[]> pacificq = new LinkedList<>();
Queue<int[]> atlanticq = new LinkedList<>();
for (int i = 0; i < M; i++) {
if (i == 0) {
Arrays.fill(pacific[i], true); // top line
for (int j = 0; j < N; j++) {
pacific[i][j] = true;
pacificq.add({i, j});
}
atlanticq.add({i, N - 1});
} else if (i == M - 1) {
Arrays.fill(atlantic[i], true); // bottom line
for (int j = 0; j < N; j++) {
atlantic[i][j] = true;
atlanticq.add({i, j});
}
pacificq.add({i, 0});
} else {
pacific[i][0] = true; // left line
atlantic[i][N - 1] = true; // right line
}
}
BFS(pacific, pacificq, matrix);
BFS(atlantic, atlanticq, matrix);
for (int row = 0; row < M; row++) {
for (int col = 0; col < N; col++) {
if (pacific[row][col] && atlantic[row][col]) {
res.add(new int[]{row, col});
}
}
}
return res;
}
private void BFS(boolean[][] status, Queue<int[]> queue, int[][] matrix) {
while (!queue.isEmpty()) {
int curr = queue.poll();
for(int[] d: dir) {
int row = curr[0] + d[0];
int col = curr[1] + d[1];
if (row < 0 || row > matrix.length - 1 || col < 0 || col > matrix.length - 1 || status[row][col] || matrix[curr[0]][curr[1]] < matrix[row][col]) {
continue;
}
status[row][col] = true;
queue.add({row, col});
}
}
}

Union Find

这一题让我想起了 percolation ,从某一边可以通道另一条变到另一边,如果某个点能同时通向两个边,那就能流到大海!
Union Find 文章点这里:Union Find