0

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

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

例子

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.
4

1 回答 1

1

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

在这个例子中，Disjoint-set ( 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我们可以访问云的“代表”，因此我们可以知道云的数量。

于 2017-05-21T05:35:15.083 回答