二维矩阵遍历框架

#算法/DFS

岛屿系列题目的核心考点就是: 用 DFS/BFS 算法遍历二维数组,本文都使用 DFS 算法

  • 二维矩阵本质上是一幅「图」
  • 所以遍历的过程中需要一个 visited 布尔数组防止走回头路
// 二维矩阵遍历框架
var dfs = function (grid, i, j, visited) {
  var m = grid.length,
    n = grid[0].length;

  if (i < 0 || j < 0 || i >= m || j >= n) {
    // 超出索引边界
    return;
  }

  if (visited[i][j]) {
    // 已遍历过 (i, j)
    return;
  }

  // 进入当前节点 (i, j)
  visited[i][j] = true;

  // 进入相邻节点(四叉树)
  // 上
  dfs(grid, i - 1, j, visited);
  // 下
  dfs(grid, i + 1, j, visited);
  // 左
  dfs(grid, i, j - 1, visited);
  // 右
  dfs(grid, i, j + 1, visited);
};