问题描述
You are given an m x n integer matrix heights representing the height of each unit cell in a continent. The Pacific ocean touches the continent’s left and top edges, and the Atlantic ocean touches the continent’s right and bottom edges.
Water can only flow in four directions: up, down, left, and right. Water flows from a cell to an adjacent one with an equal or lower height.
Return a list of grid coordinates where water can flow to both the Pacific and Atlantic oceans.
Example 1:
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4] ]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0] ]
Example 2:
Input: heights = [[2,1],[1,2] ]
Output: [[0,0],[0,1],[1,0],[1,1] ]
Constraints:
- m == heights.length
- n == heights[i].length
- 1 <= m, n <= 200
- 1 <= heights[i][j] <= 10^5
问题分析
问题要求的是能够同时流入到pacific和atlantic中的点；那么显然，左下角和右上角的点天然是满足要求的。
以第一列点为例，它们能够流入pacific，那么我们只需要想办法知道这些点能否通过邻接的点与能够流入atlantic的点相交即可。这里，我们考虑dfs，依次进行尝试；将能够流入pacific的点找出来，再用同样的方法找出能够流入atlantic的点，最后判断这些点相交的部分即为最终答案。
初始解法如下
初始解法
// slow solution
func pacificAtlantic(matrix [][]int) [][]int {
ans := [][]int{}
rows := len(matrix)
if rows == 0 {
return ans
}
cols := len(matrix[0])
if cols == 0 {
return ans
}
// 找出能够流入pacific的点
anspacific := make(map[int]bool)
for row := 0; row < rows; row++ {
for col := 0; col < cols; col++ {
// 初始访问过的点为空
// 二维的visited初始化略麻烦，这里我们将二维点坐标转换为一维，方便处理
visited := make(map[int]bool)
if canFlow("pacific", matrix, visited, row, col, rows, cols) {
anspacific[row*cols+col] = true
}
}
}
// 找出能够流入atlantic的点
ansatlantic := make(map[int]bool)
for row := rows - 1; row >= 0; row-- {
for col := cols - 1; col >= 0; col-- {
visited := make(map[int]bool)
if canFlow("atlantic", matrix, visited, row, col, rows, cols) {
ansatlantic[row*cols+col] = true
}
}
}
// 判断相交的点
for k := range anspacific {
if _, ok := ansatlantic[k]; ok {
row := k / cols
col := k % cols
ans = append(ans, []int{row, col})
}
}
return ans
}
func canFlow(which string, matrix [][]int, visited map[int]bool, row int, col int, rows int, cols int) bool {
spew.Dump(1)
//fmt.Printf("[%d, %d]\n", row, col)
//spew.Dump(visited)
if which == "pacific" && (row == 0 || col == 0) {
return true
}
if which == "atlantic" && (row == rows-1 || col == cols-1) {
return true
}
idx := row*cols + col
if _, ok := visited[idx]; ok {
return visited[idx]
}
visited[idx] = false
res := false
if row > 0 {
idxtop := idx - cols
if _, ok := visited[idxtop]; !ok && matrix[row][col] >= matrix[row-1][col] {
res = res || canFlow(which, matrix, visited, row-1, col, rows, cols)
if res {
visited[idx] = true
return res
}
}
}
if col > 0 {
idxleft := idx - 1
if _, ok := visited[idxleft]; !ok && matrix[row][col] >= matrix[row][col-1] {
res = res || canFlow(which, matrix, visited, row, col-1, rows, cols)
if res {
visited[idx] = true
return res
}
}
}
if row < rows-1 {
idxbottom := idx + cols
if _, ok := visited[idxbottom]; !ok && matrix[row][col] >= matrix[row+1][col] {
res = res || canFlow(which, matrix, visited, row+1, col, rows, cols)
if res {
visited[idx] = true
return res
}
}
}
if col < cols-1 {
idxright := idx + 1
if _, ok := visited[idxright]; !ok && matrix[row][col] >= matrix[row][col+1] {
res = res || canFlow(which, matrix, visited, row, col+1, rows, cols)
if res {
visited[idx] = true
return res
}
}
}
visited[idx] = res
return res
}
优化解法
初始解法略冗长，看了评论区后；发现基本逻辑还是dfs，只不过对于matrix的dfs有个简化处理，即定义一个directions坐标偏移量，当前坐标依次加上其中的偏移量，即可得到上下左右4个相邻点的坐标，代码要简化不少
优化代码如下
var directions [][]int
// dfs
func pacificAtlanticV2(matrix [][]int) [][]int {
ans := [][]int{}
rows := len(matrix)
if rows == 0 {
return ans
}
cols := len(matrix[0])
if cols == 0 {
return ans
}
directions = [][]int{
{0, 1},
{1, 0},
{0, -1},
{-1, 0},
}
pac, atl := make(map[int]struct{}), make(map[int]struct{})
for i := 0; i < rows; i++ {
//pac[i] = struct{}{}
//atl[(rows-1)*cols+i] = struct{}{}
dfs(matrix, pac, i, 0, rows, cols)
dfs(matrix, atl, i, cols-1, rows, cols)
}
for i := 0; i < cols; i++ {
//pac[cols*i] = struct{}{}
//atl[cols*i+cols-1] = struct{}{}
dfs(matrix, pac, 0, i, rows, cols)
dfs(matrix, atl, rows-1, i, rows, cols)
}
for k := range pac {
if _, ok := atl[k]; ok {
row := k / cols
col := k % cols
ans = append(ans, []int{row, col})
}
}
return ans
}
func dfs(matrix [][]int, visited map[int]struct{}, row int, col int, rows int, cols int) {
visited[row*cols+col] = struct{}{}
for _, v := range directions {
rownext, colnext := row+v[0], col+v[1]
if rownext < 0 || colnext < 0 || rownext >= rows || colnext >= cols || matrix[rownext][colnext] < matrix[row][col] {
continue
}
if _, ok := visited[rownext*cols+colnext]; ok {
continue
}
dfs(matrix, visited, rownext, colnext, rows, cols)
}
}