深度优先搜索（DFS）

在树的遍历方式中，深度优先搜索法与广度优先搜索算是最常用的手段了。这一篇来聊聊深度优先搜索。

深度优先搜索，本质上就是回溯算法，是一个构建并遍历决策树的过程。

既然是遍历树，那么自然就离不了树的前中后序遍历。实际上，这三种遍历法其实都是深度优先搜索的一种体现。

DFS 要理解不难，难点在于如何善于利用题目特征，巧妙的进行剪枝，从而规避问题或复杂度。

Flood Fill 系列

像经典的岛屿系列问题，用的就是Flood Fill的思路来解决的。

重点有几个：

1. 善用方向数组解决递归选择
2. 使用 visited 数组记录已经被遍历过的节点。当然，这个有时可以通过Flood Fill淹没掉遍历节点来节省空间复杂度。

Flood Fill 解题思路框架如下，该情况下不需要记录 visited 数组，也不需要撤销选择状态：

const direction = [
  [-1, 0],
  [1, 0],
  [0, -1],
  [0, 1]
];

function backtrack(row: number, col: number) {
  // 越界处理
  if (row < 0 || col < 0 || row >= rowLen || col >= colLen) return;
  // 非目标节点
  if (grid[row][col] !== 目标值) return;

  // 做选择
  grid[row][col] = 目标值;

  for (const [i, j] of direction) {
    backtrack(row + i, col + j);
  }
}

因此，我们可以总结出解决 DFS 问题的一般步骤：

  function dfs(curr) {
    if (visited[curr] || curr 越界 || curr 不满足要求) return;

    // 做选择
    visited[curr] = true;

    // ... 更新目标值

    for (const new of 新产生的情况) {
      // 进入下一次递归
      dfs(new);
    }
  }

题型参考：

1. [733] 图像渲染
2. [695] 岛屿的最大面积
3. [200] 岛屿数量
4. [130] 被围绕的区域
5. [547] 省份数量
6. [1254] 统计封闭岛屿的数目