417.太平洋大西洋水流问题
417.太平洋大西洋水流问题
题解
题目：高处的水往低处的流，左上是A，右下是B，求能流进A，又能流进B的点的坐标
思路：DFS或者BFS
1. 从低处染色到高处 2. 由于左上是A，所以连接左上的所有点都应该染A，并且都走一遍BFS或者DFS，右下同理 3. 这样A和B的交集就是答案（代码中mp1和mp2）
代码
type pair struct { x, y int } var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} func pacificAtlantic(heights [][]int) [][]int { n, m := len(heights), len(heights[0]) mp1 := make(map[pair]bool) mp2 := make(map[pair]bool) var dfs func(cur pair, mp map[pair]bool) dfs = func(cur pair, mp map[pair]bool) { if mp[cur] { return } x, y := cur.x, cur.y mp[cur] = true for _, v := range dirs { nx, ny := x+v.x, y+v.y if nx >= 0 && nx < n && ny >= 0 && ny < m && heights[x][y] <= heights[nx][ny] { dfs(pair{nx, ny}, mp) } } } for i := 0; i < n; i++ { dfs(pair{i, 0}, mp1) } for i := 0; i < m; i++ { dfs(pair{0, i}, mp1) } for i := 0; i < n; i++ { dfs(pair{i, m - 1}, mp2) } for i := 0; i < m; i++ { dfs(pair{n - 1, i}, mp2) } ans := make([][]int, 0) for k := range mp1 { if _, ok := mp2[k]; ok { ans = append(ans, []int{k.x, k.y}) } } return ans }
type pair struct { x, y int } var dirs = []pair{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} func pacificAtlantic(heights [][]int) [][]int { n, m := len(heights), len(heights[0]) mp1 := make(map[pair]bool) mp2 := make(map[pair]bool) var bfs func(cur pair, mp map[pair]bool) bfs = func(cur pair, mp map[pair]bool) { mp[cur] = true queue := []pair{cur} for len(queue) != 0 { top := queue[0] queue = queue[1:] for _, v := range dirs { nx, ny := top.x+v.x, top.y+v.y temp := pair{nx, ny} if nx >= 0 && nx < n && ny >= 0 && ny < m && !mp[temp] && heights[top.x][top.y] <= heights[nx][ny] { queue = append(queue, temp) mp[temp] = true } } } } for i := 0; i < n; i++ { bfs(pair{i, 0}, mp1) } for i := 0; i < m; i++ { bfs(pair{0, i}, mp1) } for i := 0; i < n; i++ { bfs(pair{i, m - 1}, mp2) } for i := 0; i < m; i++ { bfs(pair{n - 1, i}, mp2) } ans := make([][]int, 0) for k := range mp1 { if _, ok := mp2[k]; ok { ans = append(ans, []int{k.x, k.y}) } } return ans }
