怎么统计每组有效方格数？

Question

编辑：我有一个逻辑错误，我不知道如何修复它。这是我的密码。我认为问题出在第245行的while函数中。它没有向队列添加下一个有效像素，因此队列变为0，并退出while函数。

我需要一个老兵的帮助！我有一个类似国际象棋桌子的东西，有大小相等的方块，从下到上，从右到左编号，但只有一部分对我有效(如我发布链接的图片所示)。我从表中删除了无效的。

我希望我的C程序计算每组中的正方形。正如您在图像中看到的，有效组仅具有直接连接的正方形，而仅对角线连接的正方形不在同一组中。我用颜色来证明我的照片中的有效组。

我知道表格的宽度和高度，我知道它有多少个正方形和有效的正方形。我把它们的数字存储在一个向量中，但是我不知道如何计算每组中的正方形。我该怎么做呢？

这是我的照片：

我想找出一种适用于较大“棋盘”的方法，如已知大小的图片。

Answer 1

您正在搜索一种称为连接组件的东西。

这篇文章对这个主题有一些启发，但Web上有许多不同的实现。

Answer 2

应将每个连接的正方形分类为单个组件，并计算每个组件的大小。为此，您可以使用嵌套数据结构（如 vector）来存储连接的正方形，并将其嵌套在地图中以区分其他连接的正方形。喜欢

map<int squareIndex, vector<squares> >

基本思想是有一个< code>visited数组，这样你就可以忽略已经访问过的方块。该算法就像在< code >图形中进行< code >广度优先搜索一样。您可以使用< code >队列来存储当前正方形的相邻连接组件。我建议做以下事情。

阿尔戈

< li >从1到N遍历数组 < li >如果队列为空，则在< code>map中创建新索引，并将元素推入您的< code>map < li >如果visited[element]为真，则转到步骤1，else visited[element]=真，并将元素推送到地图中。 < li>element = dequeue() < li >将当前元素的相邻方块排队，并对当前元素从步骤2开始重复

这样，最终你的< code >地图的大小将为4(对于给定的情况)，并且每个地图元素将包含一个相连方块的向量。使用每个向量的size属性来计算每个索引中的方块数。

Answer 3

你肯定会错过的是：一个有效的正方形属于哪个组？
你可以用图论来解决这个问题。但您也可以尝试其他方法。

例如，您可以使用一个标记列表来跟踪已经访问过的节点。您可以使用vector of vector来管理组节点。

1. 以相同的方向浏览表格，比如从左上角到右下角。仅检查未访问的节点。
2. 当找到未被访问的有效方块时，将此节点添加到 vector[count] 并将此节点标记为已访问。
3. 在右下角寻找这个节点连接的正方形。如果找到一个，则将其标记为已访问，并将节点添加到同一个向量[count]列表中。
4. 重复相同的过程，直到找不到再连接的组件（例如递归）。
5. 如果在同一组中不再找到连接的正方形，请继续执行步骤 1。
6. 最后只是每个向量[count]的总和，它应该给出预期的结果（为了提高性能，你可以在查看连接的组件时动态执行此操作）。