反向搜索：深度优先搜索和广度优先搜索，三状态标记法，求解《417. 太平洋大西洋水流问题》

有一种热爱是双向奔赴。反向搜索，深度优先搜索和广度优先搜索，三状态标记法，求解《417. 太平洋大西洋水流问题》

反向搜索

• 将目标点作为已知点，反向搜索

三状态标记法

• 未访问过点标记为 0
• A 访问过点标记为 1
• B 访问过点标记为 2
  • 搜索 B 时，到达 A 访问过的点，即 A B 都能访问的点

例题

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];
                }
            }
        }
    }
}