417. 太平洋大西洋水流问题
问题描述
有一个 m × n 的矩形岛屿，与 太平洋 和 大西洋 相邻。
“太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。
这个岛被分割成一个由若干方形单元格组成的网格。
给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。
岛上雨水较多，如果相邻单元格的高度 小于或等于 当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。
返回 网格坐标 result 的 2D列表 ，其中 result[i] = [ri, ci] 表示雨水可以从单元格 (ri, ci) 流向 太平洋和大西洋 。
简单描述一下题目，雨水只能从高的地方流向低的地方，求二维表格中哪些坐标的雨水既可以流入太平洋又可以流入大西洋。
思路
整理题意，需要我们统计能够同时流向两片海域的格子。
从源点（格子）流向汇点（海域）是按照高度从高到低（非严格）的规则，那么反过来从海域到格子则是按照从低到高（非严格）规则进行，同时本身处于边缘的格子与海域联通。
因此我们可以使用两遍 DFS/BFS 进行求解：分别从与当前海域直接相连的边缘格子出发，统计能够流向当前海域的格子集合，两片海域求得的集合交集即是答案。
题解
BFS（多源 BFS）
使用 BFS 进行求解：目的是构造出两个记录矩阵 visited1 和 resvisited2 记录的节点是否遍历过，因为有if判断，所以只要遍历过，一定是可以流向海洋1 or 海洋2， 起始将所有与海域相连的格子放入队列，然后跑一遍 BFS ，所有能够进入队列的格子均能够与海域联通。
最后统计所有满足 visited1[i][j]=visited2[i][j]=true 的格子即是答案。
代码：
// 边界长度，m，n var m, n = 0, 0 var g [][]int func pacificAtlantic(heights [][]int) [][]int { g = heights // 行 m = len(g) // 列 n = len(g[0]) // 用于存放可以到海洋1、海洋2 的格子位置 var d1, d2 [][]int var visited1, visited2 = make([][]bool, m), make([][]bool, m) // 初始化 d1,d2 visited1,visited2 // 因为最外围那一圈格子是直接与海洋1或海洋2相连的 直接标记即可 for i := 0; i < m; i++ { visited1[i] = make([]bool, n) visited2[i] = make([]bool, n) for j := 0; j < n; j++ { // 顶部的一行或者左边的一列 // 可流入海洋1 更新visited1对应值,将坐标(i,j)加入d1中 if i == 0 || j == 0 { visited1[i][j] = true d1 = append(d1, []int{i, j}) } // 底部的那一行和右边的那一列 // 可以流入海洋2，更新visited2对应值,将坐标(i,j)加入d2中 if i == m-1 || j == n-1 { visited2[i][j] = true d2 = append(d2, []int{i, j}) } } } // 对初始化后的d1的每个点开始进行广度优先搜索 bfs(&d1, visited1) // 对初始化后的d2的每个点开始进行广度优先搜索 bfs(&d2, visited2) var ans [][]int // 取并集 for i := 0; i < m; i++ { for j := 0; j < n; j++ { // 既可以流入海洋1，也可以流入海洋2 if visited1[i][j] && visited2[i][j] { ans = append(ans, []int{i, j}) } } } return ans } // 分别代表从当前位置(i,j)向下、上、右、左移动（看上面的图就明白了） var directs = [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} // 广度优先搜索，从初始化后的d1和d2的每个点开始进行广度优先搜索 // d1: [[0 0] [0 1] [0 2] [0 3] [0 4] [1 0] [2 0] [3 0] [4 0]] // d2: [[0 4] [1 4] [2 4] [3 4] [4 0] [4 1] [4 2] [4 3] [4 4]] func bfs(d *[][]int, visited [][]bool) { for len(*d) != 0 { info := (*d)[0] x := info[0] y := info[1] t := g[x][y] // 对(x,y)进行移动 方向就是上下左右，nx,ny就是移动后的坐标 for _, direct := range directs { nx := x + direct[0] ny := y + direct[1] // 检查移动后 是否越界 if nx < 0 || nx >= m || ny < 0 || ny >= n { continue } // 检查该点是否可以到海洋x(你让bfs的是d1和visited1 这里就是海洋1,同样...就是海洋2) // visited[nx][ny]: 移动后的格子是否遍历过，并且可以进入海洋x // g[nx][ny]<t: 移动后的位置是否比移动前的位置低，如果低的话，就不满足题意 if visited[nx][ny] || g[nx][ny] < t { continue } // 如果上面两个检查都通过了，说明符合要去 // 加入到对应切片d和更新visited对应值即可 *d = append(*d, []int{nx, ny}) visited[nx][ny] = true } *d = (*d)[1:] } }
提交结果：
DFS：
道理同BFS
代码：
// 该题是一个二维平面回溯算法的题目 // 边界长度，m var m, n = 0, 0 var g [][]int func pacificAtlantic(heights [][]int) [][]int { g = heights // 行 m = len(g) // 列 n = len(g[0]) // 记录的节点是否遍历过，因为有if判断，所以只要遍历过，一定是可以流向海洋1 or 海洋2 var visited1, visited2 = make([][]bool, m), make([][]bool, m) for i := 0; i < m; i++ { visited1[i] = make([]bool, n) visited2[i] = make([]bool, n) } // 第一个点(0,0)开始 进行深度优先搜索 for i := 0; i < m; i++ { for j := 0; j < n; j++ { // 顶部的一行或者左边的一列，可以流入海洋1 if i == 0 || j == 0 { // 如果没有遍历过，进行深度优先搜索 if !visited1[i][j] { dfs(i, j, visited1) } } // 底部的那一行和右边的那一列，可以流入海洋2 if i == m-1 || j == n-1 { // 如果没有遍历过，进行深度优先搜索 if !visited2[i][j] { dfs(i, j, visited2) } } } } var ans [][]int // 取并集 for i := 0; i < m; i++ { for j := 0; j < n; j++ { // 既可以流入海洋1，也可以流入海洋2 if visited1[i][j] && visited2[i][j] { ans = append(ans, []int{i, j}) } } } return ans } // 分别代表从当前位置(i,j)向下、上、右、左移动（看上面的图就明白了） var directs = [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}} func dfs(x, y int, visited [][]bool) { visited[x][y] = true for _, direct := range directs { nx := x + direct[0] ny := y + direct[1] // 检查移动后 是否越界 if nx < 0 || nx >= m || ny < 0 || ny >= n { continue } // 检查该点是否可以到海洋x (你让bfs的是d1和visited1 这里就是海洋1,同样...就是海洋2) // visited[nx][ny]: 移动后的格子是否遍历过 // g[nx][ny]<t: 移动后的位置是否比移动前的位置低，如果低的话，就不满足题意 if visited[nx][ny] || g[nx][ny] < g[x][y] { continue } // 如果(nx,ny)满足条件，就继续深度优先搜索 dfs(nx, ny, visited) } }
提交结果：
