arrays - 在数组中查找 block

Question

我正在查看一些面试问题，我偶然发现了这个问题:

有一个 m x n 数组。数组中的 block 用 1 表示，0 表示没有 block 。您应该找到数组中对象的数量。对象只不过是一组水平和/或垂直连接的 block 。

例如

0 1 0 0
0 1 0 0
0 1 1 0
0 0 0 0
0 1 1 0

答案:这个数组中有 2 个对象。 L形物体和最后一行的物体。

我在想出一个可以捕获“u”(如下所示)形状的算法时遇到了麻烦。我应该如何处理这个问题？

0 1 0 1
0 1 0 1
0 1 1 1
0 0 0 0
0 1 1 0

Answer 1

一种方法是使用 Flood Fill .该算法将是这样的:

for row in block_array:
    for block in row:
        if BLOCK IS A ONE and BLOCK NOT VISITED: 
            FLOOD_FILL starting from BLOCK

您可以标记在填充过程中访问过的项目，并从那里跟踪形状。