图遍历计数云 [python]

Question

给定一个由“1”（云）和“0”（晴空）组成的二维网格天空地图，计算云的数量。

一朵云被晴朗的天空包围着，由相邻的云水平或垂直连接而成。您可以假设 skyMap 的所有四个边都被晴朗的天空包围。

例子

skyMap = [['0', '1', '1', '0', '1'],
          ['0', '1', '1', '1', '1'],
          ['0', '0', '0', '0', '1'],
          ['1', '0', '0', '1', '1']]

输出应该是

countClouds(skyMap) = 2;

对于

skyMap = [['0', '1', '0', '0', '1'],
          ['1', '1', '0', '0', '0'],
          ['0', '0', '1', '0', '1'],
          ['0', '0', '1', '1', '0'],
          ['1', '0', '1', '1', '0']]

输出应该是

countClouds(skyMap) = 5.

Answer 1

这可以通过直接在天空图矩阵上计算连通分量来解决。我们可以使用Disjoint-set.

这样的数据结构

在此示例中，Disjoint-set (UnionFind) 的实现取自 here:

refs = [[0, 0], [-1, 0], [0, -1], [1, 0], [0, 1]]
for i in range(len(skyMap)):
    for j in range(len(skyMap[i])):
        print i, j
        for dy, dx in refs:
            is_neighbour_valid = 0 <= (i + dy) < len(skyMap) and 0 <= (j + dx) < len(skyMap[i])
            if not is_neighbour_valid:
                continue

            current_cell, neighbour_cell = skyMap[i][j] == '1', skyMap[i + dy][j + dx] == '1'
            if current_cell and is_neighbour_valid:
                ds.union((i, j), (i + dy, j + dx))

# The number of connected components:
print len(set(ds.parents.values()))

对于每个值为 '1' 的条目，我们创建一个集合。如果它与另一个这样的条目相邻，我们将这两个集合结合起来。最后，我们得到一组不相交的集合，每个集合代表一朵云。在这段代码中，ds.parents 让我们可以访问云的 "representatives"，因此我们可以知道云的数量。

图遍历计数云 [python]

Graph Traversal count clouds [python]

python

graph-traversal

disjoint-sets

disjoint-union