寻找共同整数的Int [][]搜索

Question

我有一个结构为int[][]的数组，大小固定。它被填充了自然数。例如：

0 0 0 0 0 0 0
1 2 6 9 0 3 4
3 1 3 4 5 6 0
1 2 3 0 2 1 1
1 2 0 0 0 1 0

我的目标是检查在这个结构中有多少个零的“圆圈”。在这个例子中，答案应该是4。
编辑
一个圆圈是包含所有联通的零的结构。什么意思？这些零可以从一个零向上、下、左或右到达（不考虑对角线）。
示例解决方案：
第一个圆圈：

0 0 0 0 0 0 0
1 2 6 9 0 3 4
3 1 3 4 5 6 0
1 2 3 0 2 1 1
1 2 0 0 0 1 0

第二个圆圈：

0 0 0 0 0 0 0
1 2 6 9 0 3 4
3 1 3 4 5 6 0
1 2 3 0 2 1 1
1 2 0 0 0 1 0

第三个圆圈：

0 0 0 0 0 0 0
1 2 6 9 0 3 4
3 1 3 4 5 6 0
1 2 3 0 2 1 1
1 2 0 0 0 1 0

第四个圆圈：

0 0 0 0 0 0 0
1 2 6 9 0 3 4
3 1 3 4 5 6 0
1 2 3 0 2 1 1
1 2 0 0 0 1 0

- Maciej Miśkiewicz

---

一个圆包含了所有的零点。 - Maciej Miśkiewicz

如果您想从我们的日常工作中抽出一点时间，请花些时间充分描述您的措辞。什么是“圆形”？什么是“联合零点”？不要假设我们熟悉您特定的领域。 - Special Sauce

@SpecialSauce请查看编辑，希望它能够澄清。 - Maciej Miśkiewicz

感谢您编辑：现在清楚了您的意思是“相邻区域”。 - Special Sauce

@SpecialSauce 是的，我很抱歉让你感到困惑。 - Maciej Miśkiewicz

Answer 1

这个示例算法相当简单。

1. 从未检查过的位置开始。
2. 找到与相邻零值相连的零值。
3. 将找到的零值更改为1。[类似于泛洪填充]
4. 递增计数器。
5. 如果没有检查完所有位置，请返回到步骤2。
6. 否则：报告结果。

你可能想研究一下Flood fill算法，像这里：

https://en.wikipedia.org/wiki/Flood_fill

---

或者 - 更有趣的方法。

定义一个圆形类，其中包含像素[x,y]的集合

1. 找到所有单个零值的位置[x,y]
2. 让每个单独的零值成为一个单独的“圆形”
3. 将相邻的圆形合并成较大的“圆形”
4. 保持合并(3-4)直到没有进展为止。
5. 报告结果。

在这种情况下，适当的排序将是关键因素。
您将需要一个函数来检查两个圆形是否相邻。
这会更加有趣!

- Witold Kaczurba

---

那是我最初的想法！但由于递归，它占用了太多的内存资源。然后，我采用了非递归的方法，但效果并不好。 - Maciej Miśkiewicz

好的，马切伊。我给你另一个备选方案 :)。 - Witold Kaczurba

Answer 2

我认为你需要的是斑点检测器，一种图像处理算法，可以找到共享某些属性（如灰度值）的相邻像素。 OpenCV内置了斑点检测器。使用教程可以在这里找到。

你还可以查看连通组件标记。你可以根据给定的伪代码实现它（你想避免使用外部库），它不包含递归（你对Vito的回答的评论）。

- rics

---

首先，非常感谢您的帮助。然而，我只使用简单的int[][]，不应导入任何外部库。我应该有一个直接的函数，它以这个int[][]作为参数，并返回一个名为“blobs”的单个int meanint数字。 - Maciej Miśkiewicz