图遍历计数云[python]

Question

给定一个由'1's (云)和'0's (晴空)组成的二维网格skyMap，计算云的数量。

云被晴朗的天空所包围，由相邻的云水平或垂直连接而成。你可以假设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

这可以通过直接在星图矩阵上计算连通分量来解决。我们可以使用不相交集的数据结构。

在本例中，不相交集(UnionFind)的实现是从这里中提取的。

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允许我们访问云的“代表”，这样我们就可以知道云的数量。