寻求高效网格区域识别算法：16×16网格白色不相交区域划分方案

针对你提出的16×16网格白色区域识别、为每个白色格子分配唯一区域ID的需求，这里给你梳理两种高效可行的方案，并对比各自的适用场景，帮你找到最适合的实现方式：

核心需求回顾 #

我们需要遍历16×16的网格，将所有不相交的白色格子集群标记为不同的区域ID，每个白色格子对应唯一的所属区域ID，黑色格子无需标记（或标记为-1等特殊值）。

可选方案对比与选择 #

对于16×16这种极小规模的网格，两种主流算法的效率几乎没有差别，但实现复杂度和适用场景略有不同：

1. Flood Fill（BFS/DFS）—— 最直观易实现 #

这是静态网格区域识别的首选方案，代码简洁，逻辑清晰，一次性遍历即可完成标记。

• 时间复杂度：O(N)，N为网格总格子数（256），实际运行几乎瞬间完成。
• 适用场景：仅需一次性识别区域，无需后续动态修改网格的场景。

实现步骤

• 创建与网格同尺寸的region_id数组，初始值设为-1（表示未标记）。
• 初始化区域计数器current_id = 0。
• 遍历每个格子，若遇到未标记的白色格子，启动BFS/DFS，将所有连通的白色格子标记为当前current_id，然后计数器自增。

Python代码示例（BFS版本）

def assign_region_ids_flood_fill(grid):
    rows, cols = 16, 16
    region_id = [[-1 for _ in range(cols)] for _ in range(rows)]
    current_id = 0
    # 四连通方向（上下左右），若需八连通可添加对角线方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for i in range(rows):
        for j in range(cols):
            # 找到未标记的白色格子，启动BFS
            if grid[i][j] == "white" and region_id[i][j] == -1:
                queue = [(i, j)]
                region_id[i][j] = current_id
                while queue:
                    x, y = queue.pop(0)
                    # 遍历所有相邻方向
                    for dx, dy in directions:
                        nx, ny = x + dx, y + dy
                        # 检查相邻格子是否在网格内、是白色且未标记
                        if 0 <= nx < rows and 0 <= ny < cols:
                            if grid[nx][ny] == "white" and region_id[nx][ny] == -1:
                                region_id[nx][ny] = current_id
                                queue.append((nx, ny))
                current_id += 1
    return region_id

2. Union-Find（DSU，不相交集合）—— 适合动态场景 #

如果后续需要支持动态修改网格（比如某个格子变色、合并/拆分区域），Union-Find会更有优势，因为它可以高效处理集合的合并与查询操作。对于静态网格，它的效率和Flood Fill相当，但代码稍复杂。

• 时间复杂度：接近O(N)（带路径压缩和按秩合并优化），同样适合16×16的规模。
• 适用场景：需要后续动态调整网格、频繁合并/查询区域的场景。

实现步骤

• 将每个白色格子映射为一维索引（比如idx = i*16 + j），黑色格子跳过。
• 初始化Union-Find结构，每个白色格子的父节点指向自己。
• 遍历每个白色格子，合并其右侧和下侧的相邻白色格子（避免重复合并）。
• 为每个集合的根节点分配唯一区域ID，再映射回二维网格的region_id数组。

Python代码示例

class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size
    
    # 路径压缩优化
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    # 按秩合并优化
    def union(self, x, y):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        else:
            self.parent[y_root] = x_root
            if self.rank[x_root] == self.rank[y_root]:
                self.rank[x_root] += 1

def assign_region_ids_uf(grid):
    rows, cols = 16, 16
    total_cells = rows * cols
    uf = UnionFind(total_cells)
    # 只检查下、右两个方向，避免重复处理相邻格子
    directions = [(1, 0), (0, 1)]
    
    # 第一步：合并相邻的白色格子集合
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == "white":
                idx = i * cols + j
                for dx, dy in directions:
                    nx, ny = i + dx, j + dy
                    if 0 <= nx < rows and 0 <= ny < cols:
                        if grid[nx][ny] == "white":
                            neighbor_idx = nx * cols + ny
                            uf.union(idx, neighbor_idx)
    
    # 第二步：为每个集合根节点分配唯一ID
    root_to_id = {}
    current_id = 0
    region_id = [[-1 for _ in range(cols)] for _ in range(rows)]
    
    for i in range(rows):
        for j in range(cols):
            if grid[i][j] == "white":
                idx = i * cols + j
                root = uf.find(idx)
                if root not in root_to_id:
                    root_to_id[root] = current_id
                    current_id += 1
                region_id[i][j] = root_to_id[root]
    
    return region_id

总结 #

• 如果只是一次性识别区域，优先选Flood Fill，代码更简洁易维护。
• 如果需要动态修改网格并更新区域，选Union-Find，后续操作更高效。
• 两种方案都支持四连通/八连通的调整，只需修改directions数组即可。

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