写个连通域吧~_单片机连通域写法-CSDN博客

本文链接：https://blog.csdn.net/math_computer/article/details/107134353

本文介绍了一种非递归深度优先搜索算法，用于计算二维矩阵中所有连通区域的面积。该算法避免了递归可能导致的栈溢出问题，适用于大规模数据集。文章通过实例演示了算法的具体实现过程。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

def connected_regions_areas(mat):
    if not mat:
        return [], []
    regions = []
    areas = []
    m, n = len(mat), len(mat[0])
    label_table = [[0 for j in range(n)] for i in range(m)]
    label = 1
    d = [(-1, 0), (1, 0), (0, -1), (0, 1),
         (-1, 1), (-1, -1), (1, -1), (1, 1)]

    # 当指标不越界，并且值不为0，并且没有被标记过时，返回True
    def condition(mat, i, j, m, n, label_table):
        return (0 <= i < m and 0 <= j < n and mat[i][j] != 0 and label_table[i][j] == 0)

    # 返回包含(i, j)的连通区域和区域面积
    # 使用非递归实现，因为递归层次超过1000时python的栈会溢出
    def stack_dfs(mat, i, j, m, n, d, label_table, label):
        stack, count = [(i, j)], 0
        region = []
        while stack:
            i0, j0 = stack.pop()
            if condition(mat, i0, j0, m, n, label_table):
                count += 1
                region.append((i0, j0))
                label_table[i0][j0] = label

                for dx, dy in d:
                    ii, jj = i0 + dx, j0 + dy
                    if condition(mat, ii, jj, m, n, label_table):
                        stack.append((ii, jj))
        return region, count

    for i in range(m):
        for j in range(n):
            if condition(mat, i, j, m, n, label_table):
                region, count = stack_dfs(mat, i, j, m, n, d, label_table, label)
                regions.append(region)
                areas.append(count)
                label += 1
    return regions, areas


# 测试通过

for k in range(7):
    print("-" * 10 + str(k) + "-" * 10)
    m, n = k, k
    import random
    random.seed(12)
    mat = [[int(random.random() >= 0.5) for j in range(n)] for i in range(m)]
    print("[mat]:")
    for i in range(m):
        print(mat[i])
    regions, areas = connected_regions_areas(mat)
    print("[areas]:")
    print(areas)

树的前序遍历