有一种热爱是双向奔赴。反向搜索,深度优先搜索和广度优先搜索,三状态标记法,求解《417. 太平洋大西洋水流问题》
有一个 m × n 的矩形岛屿,与 太平洋 和 大西洋 相邻。 “太平洋” 处于大陆的左边界和上边界,而 “大西洋” 处于大陆的右边界和下边界。 这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights , heights[r][c] 表示坐标 (r, c) 上单元格 高于海平面的高度 。 岛上雨水较多,如果相邻单元格的高度 小于或等于 当前单元格的高度,雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。 返回网格坐标 result 的 2D 列表 ,其中 result[i] = [ri, ci] 表示雨水从单元格 (ri, ci) 流动 既可流向太平洋也可流向大西洋 。
var pacificAtlantic = function(heights) {
const m = heights.length, n = heights[0].length, r = []
const reachAble = Array.from({length: m}, _ => new Uint8Array(n))
const d = (i, j, preHeight, ocean) => {
if (i >= 0 && i < m && j >= 0 && j < n && heights[i][j] >= preHeight && reachAble[i][j] !== ocean) {
if (reachAble[i][j]) r.push([i, j])
reachAble[i][j] = ocean
d(i + 1, j, heights[i][j], ocean)
d(i - 1, j, heights[i][j], ocean)
d(i, j + 1, heights[i][j], ocean)
d(i, j - 1, heights[i][j], ocean)
}
}
for (let i = 0; i < m; i++) d(i, 0, 0, 1)
for (let j = 0; j < n; j++) d(0, j, 0, 1)
for (let i = 0; i < m; i++) d(i, n - 1, 0, 2)
for (let j = 0; j < n; j++) d(m - 1, j, 0, 2)
return r
};
func pacificAtlantic(heights [][]int) [][]int {
m, n := len(heights), len(heights[0])
var r [][]int
reachAble := make([][]int, m)
for i := 0; i < m; i++ {
reachAble[i] = make([]int, n)
}
var d func(i int, j int, preHeight int, ocean int)
d = func(i int, j int, preHeight int, ocean int) {
if i >= 0 && i < m && j >= 0 && j < n && heights[i][j] >= preHeight && reachAble[i][j] != ocean {
if reachAble[i][j] > 0 {
r = append(r, []int{i, j})
}
reachAble[i][j] = ocean
d(i + 1, j, heights[i][j], ocean)
d(i - 1, j, heights[i][j], ocean)
d(i, j + 1, heights[i][j], ocean)
d(i, j - 1, heights[i][j], ocean)
}
}
for i := 0; i < m; i++ {
d(i, 0, 0, 1)
}
for j := 0; j < n; j++ {
d(0, j, 0, 1)
}
for i := 0; i < m; i++ {
d(i, n - 1, 0, 2)
}
for j := 0; j < n; j++ {
d(m - 1, j, 0, 2)
}
return r
}
class Solution {
protected $heights;
protected $m;
protected $n;
protected $reachAble;
protected $r;
function pacificAtlantic($heights) {
$this->heights = $heights;
$this->m = $m = count($heights);
$this->n = $n = count($heights[0]);
$this->reachAble = array_fill(0, $m, array_fill(0, $n, 0));
for ($i = 0; $i < $m; $i++) $this->d($i, 0, 0, 1);
for ($j = 0; $j < $n; $j++) $this->d(0, $j, 0, 1);
for ($i = 0; $i < $m; $i++) $this->d($i, $n - 1, 0, 2);
for ($j = 0; $j < $n; $j++) $this->d($m - 1, $j, 0, 2);
return $this->r;
}
function d($i, $j, $preHeight, $ocean) {
if ($i >= 0 && $i < $this->m && $j >= 0 && $j < $this->n && $this->heights[$i][$j] >= $preHeight && $this->reachAble[$i][$j] !== $ocean) {
if ($this->reachAble[$i][$j]) $this->r []= [$i, $j];
$this->reachAble[$i][$j] = $ocean;
$this->d($i + 1, $j, $this->heights[$i][$j], $ocean);
$this->d($i - 1, $j, $this->heights[$i][$j], $ocean);
$this->d($i, $j + 1, $this->heights[$i][$j], $ocean);
$this->d($i, $j - 1, $this->heights[$i][$j], $ocean);
}
}
}
var pacificAtlantic = function(heights) {
const m = heights.length, n = heights[0].length, r = []
const reachAble = Array.from({length: m}, _ => new Uint8Array(n))
const bfs = (i, j, preHeight, ocean) => {
const q = [[i, j, preHeight]]
while (q.length) {
const [x, y, preHeight] = q.shift()
if (x >= 0 && x < m && y >= 0 && y < n && heights[x][y] >= preHeight && reachAble[x][y] !== ocean) {
if (reachAble[x][y]) r.push([x, y])
reachAble[x][y] = ocean
q.push([x + 1, y, heights[x][y]])
q.push([x - 1, y, heights[x][y]])
q.push([x, y + 1, heights[x][y]])
q.push([x, y - 1, heights[x][y]])
}
}
}
for (let i = 0; i < m; i++) bfs(i, 0, 0, 1)
for (let j = 0; j < n; j++) bfs(0, j, 0, 1)
for (let i = 0; i < m; i++) bfs(i, n - 1, 0, 2)
for (let j = 0; j < n; j++) bfs(m - 1, j, 0, 2)
return r
};
func pacificAtlantic(heights [][]int) [][]int {
m, n, dr := len(heights), len(heights[0]), [][]int
reachAble := make([][]int, m)
for i := 0; i < m; i++ {
reachAble[i] = make([]int, n)
}
var r [][]int
var bfs func(i int, j int, ocean int)
bfs = func(i int, j int, ocean int) {
q := [][]int
for len(q) > 0 {
p := q[0]
q = q[1:]
if reachAble[p[0]][p[1]] == ocean {
continue
}
if reachAble[p[0]][p[1]] > 0 {
r = append(r, []int{p[0], p[1]})
}
reachAble[p[0]][p[1]] = ocean
for _, v := range dr {
x, y := p[0] + v[0], p[1] + v[1]
if x >= 0 && x < m && y >= 0 && y < n && heights[x][y] >= heights[p[0]][p[1]] {
q = append(q, []int{x, y})
}
}
}
}
for i := 0; i < m; i++ {
bfs(i, 0, 1)
}
for j := 0; j < n; j++ {
bfs(0, j, 1)
}
for i := 0; i < m; i++ {
bfs(i, n - 1, 2)
}
for j := 0; j < n; j++ {
bfs(m - 1, j, 2)
}
return r
}
class Solution {
protected $heights;
protected $m;
protected $n;
protected $reachAble;
protected $r;
protected $dr = [[-1, 0], [1, 0], [0, 1], [0, -1]];
function pacificAtlantic($heights) {
$this->heights = $heights;
$this->m = $m = count($heights);
$this->n = $n = count($heights[0]);
$this->reachAble = array_fill(0, $m, array_fill(0, $n, 0));
for ($i = 0; $i < $m; $i++) $this->bfs($i, 0, 1);
for ($j = 0; $j < $n; $j++) $this->bfs(0, $j, 1);
for ($i = 0; $i < $m; $i++) $this->bfs($i, $n - 1, 2);
for ($j = 0; $j < $n; $j++) $this->bfs($m - 1, $j, 2);
return $this->r;
}
function bfs($i, $j, $ocean) {
$q = [[$i, $j]];
while (count($q)) {
$p = array_pop($q);
if ($this->reachAble[$p[0]][$p[1]] === $ocean) continue;
if ($this->reachAble[$p[0]][$p[1]]) $this->r []= $p;
$this->reachAble[$p[0]][$p[1]] = $ocean;
foreach ($this->dr as $d) {
$x = $p[0] + $d[0];
$y = $p[1] + $d[1];
if ($x >= 0 && $x < $this->m && $y >= 0 && $y < $this->n && $this->heights[$x][$y] >= $this->heights[$p[0]][$p[1]]) {
$q []= [$x, $y];
}
}
}
}
}