0

假设我有一个 0 和 1 的矩阵。现在我想计算矩阵中仅包含 1 的所有连续区域。

分配一个“已访问”的新矩阵来跟踪已访问的元素
计数 = 0
对于矩阵中的每个元素 E
  如果 E == 1 且 E 未被访问
    计数 = 计数 + 1
    运行 BFS/DFS 访问连接到 E 的所有未访问的矩阵元素
返回 COUNT

如果矩阵是 N x N，那么我们需要额外的 N x N“已访问”矩阵以及 BFS/DFS 的队列/堆栈。现在我想知道是否有一种算法可以解决这个问题并且需要更少的内存。

4

1 回答 1

1

如果内存如此关键，那么您可以使用以下方法：

另外只保留一个矩阵的一行长度的数组，然后从上到下扫描矩阵行，每次处理当前行时，其中有连续1的间隔，可以合并位于它们上面的不同块，对于例子

1110001110011
1111001110011
0011111000011

如果您只考虑前 2 行，则存在三个不同的部分，但第 3 行合并了其中的前两个。所以你可以使用额外的数组来保存不同的部分直到最后一行，即最初它将用 0 填充，当你刚开始扫描矩阵的第 3 行时，该数组应该看起来像 1111002220033，即每个数字显示该单元格属于哪个部分。处理完第 3 行后，它们将被合并，额外的数组将变为 0011111000033。因此，在扫描每一行后，一些部分被合并，一些部分消失。每次零件消失时，您都可以增加计数器以最终得到答案。

但是，这比 BFS/DFS 更棘手和复杂，我认为您在实践中无论如何都不需要使用它。

于 2013-03-21T15:45:27.623 回答