岛屿数量

问题

给定一个二维网格（可以理解为 Canvas 上的像素点），其中 1 表示黑块，0 表示空白。计算网格中黑块组成的”岛屿”数量。

岛屿由水平或垂直相邻的黑块连接而成。

输入:
[
  [1, 1, 0, 0, 0],
  [1, 1, 0, 0, 0],
  [0, 0, 1, 0, 0],
  [0, 0, 0, 1, 1]
]

输出: 3

解答

DFS 解法

function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  // 深度优先搜索，将访问过的黑块标记为 0
  function dfs(i, j) {
    // 边界检查 + 是否为黑块
    if (i < 0 || i >= rows || j < 0 || j >= cols || grid[i][j] === 0) {
      return;
    }

    // 标记为已访问
    grid[i][j] = 0;

    // 向四个方向扩展
    dfs(i - 1, j); // 上
    dfs(i + 1, j); // 下
    dfs(i, j - 1); // 左
    dfs(i, j + 1); // 右
  }

  // 遍历整个网格
  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 1) {
        count++; // 发现新岛屿
        dfs(i, j); // 淹没整个岛屿
      }
    }
  }

  return count;
}

BFS 解法

function numIslandsBFS(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
  let count = 0;

  function bfs(startI, startJ) {
    const queue = [[startI, startJ]];
    grid[startI][startJ] = 0;

    while (queue.length > 0) {
      const [i, j] = queue.shift();

      // 检查四个方向
      for (const [di, dj] of directions) {
        const ni = i + di;
        const nj = j + dj;

        if (ni >= 0 && ni < rows && nj >= 0 && nj < cols && grid[ni][nj] === 1) {
          grid[ni][nj] = 0; // 入队前标记，避免重复
          queue.push([ni, nj]);
        }
      }
    }
  }

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (grid[i][j] === 1) {
        count++;
        bfs(i, j);
      }
    }
  }

  return count;
}

Canvas 应用示例

// 从 Canvas 获取像素数据并计算黑块岛屿数量
function countBlackIslands(canvas) {
  const ctx = canvas.getContext('2d');
  const imageData = ctx.getImageData(0, 0, canvas.width, canvas.height);
  const { data, width, height } = imageData;

  // 将像素数据转换为二维网格
  // 黑色像素 (R=0, G=0, B=0) 标记为 1
  const grid = [];
  for (let i = 0; i < height; i++) {
    grid[i] = [];
    for (let j = 0; j < width; j++) {
      const idx = (i * width + j) * 4;
      const isBlack = data[idx] === 0 && data[idx + 1] === 0 && data[idx + 2] === 0;
      grid[i][j] = isBlack ? 1 : 0;
    }
  }

  return numIslands(grid);
}

关键点

• 原地修改：将访问过的格子置为 0，省去 visited 数组
• DFS vs BFS：DFS 代码简洁，BFS 避免栈溢出（大网格时更安全）
• 入队时标记：BFS 中在入队前标记已访问，避免重复入队
• 四方向遍历：只考虑上下左右，不含对角线
• 时间复杂度：O(m × n)，每个格子最多访问一次