Relog JOURNAL
返回归档

RELOG / ARTICLE

洪水填充算法判断地图是否有封闭区域

K

修订说明（2026-11）：原文称“不指定出生点时只检查每个格子的邻居就能判断连通”，这是错误的。局部邻居情况不能证明整张地图连通。

假设只能上下左右移动，要判断 所有非障碍格子是否能从出生点到达 ：从出生点进行一次广度优先搜索，统计到达的非障碍格子数，再与地图上的非障碍格子总数比较。相等才说明它们属于同一个连通区域。

如果没有指定出生点，可以任选一个非障碍格子作为起点；如果要找出所有互不连通的区域，就对每个未访问的非障碍格子继续发起搜索。单纯检查每个格子是否至少有一个非障碍邻居，无法识别两个彼此隔开的区域。

using System.Collections.Generic;

/// <summary>
/// 判断所有非障碍格子是否能从指定起点到达（四方向移动）
/// </summary>
/// <param name="obstacleMap">[x,y] 为 true 表示障碍物</param>
static bool MapIsFullyAccessible(bool[,] obstacleMap, int startX, int startY)
{
    int width = obstacleMap.GetLength(0), height = obstacleMap.GetLength(1);
    if (startX < 0 || startX >= width || startY < 0 || startY >= height ||
        obstacleMap[startX, startY]) return false;

    int passableCount = 0;
    for (int x = 0; x < width; x++)
        for (int y = 0; y < height; y++)
            if (!obstacleMap[x, y]) passableCount++;

    var visited = new bool[width, height];
    var queue = new Queue<(int X, int Y)>();
    queue.Enqueue((startX, startY));
    visited[startX, startY] = true;
    int reachedCount = 0;
    (int Dx, int Dy)[] directions = { (1, 0), (-1, 0), (0, 1), (0, -1) };

    while (queue.Count > 0)
    {
        var tile = queue.Dequeue();
        reachedCount++;
        foreach (var (dx, dy) in directions)
        {
            int nx = tile.X + dx, ny = tile.Y + dy;
            if (nx < 0 || nx >= width || ny < 0 || ny >= height) continue;
            if (visited[nx, ny] || obstacleMap[nx, ny]) continue;
            visited[nx, ny] = true;
            queue.Enqueue((nx, ny));
        }
    }
    return reachedCount == passableCount;
}

参考：Red Blob Games 的网格广度优先搜索讲解、连通分量的遍历方法。

#算法

读到这里，感谢你。

回到顶部