在JavaScript中实现洪水算法，标记网格中的孤立区域

嘿，这个问题其实很好解决，用洪水填充（Flood Fill）算法就能精准标记出所有孤立的可通行区域。我给你捋捋思路，再附上可直接运行的代码示例：

• 遍历网格中的每一个单元格
• 当遇到可通行（walkable为true）且未被标记的单元格时，启动一次洪水填充
• 用唯一的区域ID标记这次填充覆盖的所有连通单元格
• 每完成一次填充，区域ID递增，确保每个孤立区域都有独特的标识

首先假设你的网格结构是这样的（和你描述的一致）：

// 示例网格：每个单元格包含walkable布尔属性
const grid = [
  [{walkable: true}, {walkable: true}, {walkable: false}, {walkable: true}],
  [{walkable: true}, {walkable: false}, {walkable: false}, {walkable: true}],
  [{walkable: true}, {walkable: true}, {walkable: true}, {walkable: true}],
  [{walkable: false}, {walkable: false}, {walkable: true}, {walkable: false}]
];

接下来是标记孤立区域的核心函数（用迭代式实现，避免大网格递归栈溢出）：

function markIsolatedRegions(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  // 创建标记数组，0代表未标记，后续用正整数作为区域ID
  const regionMarks = Array(rows).fill().map(() => Array(cols).fill(0));
  let currentRegionId = 1;

  // 迭代式洪水填充：用队列处理待遍历的单元格
  function floodFill(startRow, startCol) {
    const queue = [[startRow, startCol]];
    regionMarks[startRow][startCol] = currentRegionId;

    // 上下左右四个移动方向
    const directions = [[-1,0], [1,0], [0,-1], [0,1]];

    while (queue.length > 0) {
      const [row, col] = queue.shift();
      
      // 遍历四个方向的相邻单元格
      for (const [dr, dc] of directions) {
        const newRow = row + dr;
        const newCol = col + dc;

        // 校验：在网格范围内、可通行、未被标记
        if (
          newRow >= 0 && newRow < rows &&
          newCol >= 0 && newCol < cols &&
          grid[newRow][newCol].walkable &&
          regionMarks[newRow][newCol] === 0
        ) {
          regionMarks[newRow][newCol] = currentRegionId;
          queue.push([newRow, newCol]);
        }
      }
    }
  }

  // 遍历整个网格，启动洪水填充
  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col].walkable && regionMarks[row][col] === 0) {
        floodFill(row, col);
        currentRegionId++; // 完成一个区域，ID递增
      }
    }
  }

  return regionMarks;
}

• regionMarks数组和原网格尺寸一致，专门记录每个单元格所属的区域ID
• 用队列实现迭代式洪水填充，比递归更安全，不会因为网格过大导致栈溢出
• 每次找到未标记的可通行单元格，就用当前ID填充所有连通的可通行区域，确保每个孤立区域的ID唯一
• 方向数组覆盖上下左右四个相邻单元格，保证不会漏掉任何连通的区域

比如全可通行的网格：

const fullWalkableGrid = [
  [{walkable: true}, {walkable: true}],
  [{walkable: true}, {walkable: true}]
];

console.log(markIsolatedRegions(fullWalkableGrid));
// 输出：[[1,1], [1,1]] 所有单元格都属于区域1

再比如有多个孤立区域的网格：

const gridWithIslands = [
  [{walkable: true}, {walkable: false}, {walkable: true}],
  [{walkable: true}, {walkable: false}, {walkable: true}],
  [{walkable: false}, {walkable: true}, {walkable: false}]
];

console.log(markIsolatedRegions(gridWithIslands));
// 输出：[[1,0,2], [1,0,2], [0,3,0]]
// 区域1：左上角2个单元格；区域2：右上角2个单元格；区域3：中间下方1个单元格

内容的提问来源于stack exchange，提问作者Chris Scott