0

以下数组中有多少个连通集？

1 0 0 1

0 0 1 0

0 0 1 0

1 0 0 1

“连接集”可以定义为一组小区，上面提到了 1 个小区，并且在该集中至少有一个其他小区与它们共享邻居关系。一个包含 1 的单元格并且没有包含 1 的周围邻居可以被认为是一个包含一个单元格的集合。邻居可以定义为在 8 个可能方向（即 N、W、E、S、NE、NW、SE、SW 方向）上与给定小区相邻的所有小区。一个细胞不是它自己的邻居。

实际上我被困在这个问题上并且无法理解这个问题中连接集的定义是什么意思

4

2 回答 2

2

这是突出显示集合的图像：

套

规则适用如下（据我了解）：

  • 单元格必须包含 1 才能成为集合的一部分
  • 如果相邻（上、下和对角线）单元格也包含 1，则它是同一集合的一部分。
  • 一个有 1 的单元格并且没有周围有 1 的邻居可以被认为是一个有一个单元格的集合

第三点我不太确定，因为 OP 说“'连接集'可以定义为一组单元格，其中提到了 1 并且该集中至少有一个其他单元格”，但是然后还说“一个有 1 的单元格并且没有周围的邻居有 1 可以被认为是一个有一个单元格的集合”，所以它非常模棱两可。

如果是单格不设置的情况，则计数分别为 1 和 5。

于 2012-06-27T20:32:44.607 回答
0

解决问题的一种方法是使用洪水填充算法

现在检查 1 并将其设为 0，现在检查所有方向，如果它们包含 1，则也将它们设为 0（除了在所有方向上进行递归调用之外别无他法）

整个数组检查完成后，我们面对多少次 1 是答案

例如让我们采取

1 0 0 1

1 0 0 1

1 0 0 1

1 0 1 0

现在 00 处的元素是 1 现在将其设为 0 现在检查所有方向现在我们在 10 位置有 1 因此将其设为零并再次检查我们将获得 20 和 30 位置因此计为 1

现在移动到 03 使其为 0 现在检查 1 因此包含 1 的单元格为 13 使其为零 现在移动到 23 最后到 32 并增加计数器因此它是 2

现在检查每个单元格，因为没有其他单元格包含 1，因此总连接集为 2

于 2012-07-09T05:21:12.483 回答