2

注意：对于喜欢逻辑问题等的任何人来说，这都是一个具有挑战性的问题。

考虑一个高度为 H 和宽度为 W 的矩形二维网格。网格上的每个空间都有一个值，要么0 1要么2。最初，网格上的每个空间都是 a 0，除了沿着四个边中的每一个的空间，它们最初是 a 2。

然后考虑相邻（水平或垂直）网格空间的任意路径。路径开始于 a2并结束于不同的2。路径上的每个空间都是1.

该路径将网格划分为两个0空间“扇区”。有一个物体停在一个未指定的0空间上。不包含对象的“扇区”必须用 完全填充2。

定义一个算法，该算法确定必须从 变为的空间2，0给定一个数组（列表），该数组（列表）对应于网格中的值0，从上到下1，2然后从左到右。换句话说，数组中索引 0 处的元素包含网格中左上角空间的值（最初是 a 2）。索引 1 处的元素包含网格中左侧列中的空间值，从顶部算起第二个，依此类推。索引 H 处的元素包含网格中顶行但左数第二个的空间值，依此类推。

一旦算法完成并且空的“扇区”完全被 s 填充2，SAME 算法必须足以再次执行相同的过程。第二次（和上）时间，路径仍然从 a 绘制2到不同的2，跨越 的空间0，但是“网格”更小，因为2被其他 s 包围的2s 不能被路径触及（因为路径是沿0) 的空间。

我非常感谢能够为我解决这个问题的人。这不必使用特定的编程语言；事实上，伪代码或只是英文就足够了。再次感谢！如果您有任何问题，请发表评论，我会指定需要指定的内容。

4

1 回答 1

3

在我看来，一个基本的洪水填充算法可以完成工作：

  • 扫描您的阵列以0查找您找到的第一个，然后从那里开始填充，0用其他数字填充该区域，比方说3- 这将标记您的“扇区”之一。
  • 完成后，再次扫描 a 0，然后从那里填充填充，4这次用 a 填充。
  • 在两次填充期间，您可以检查是否找到了您的对象；无论您在哪个填写期间找到它，请跟踪该数字。
  • 两次填充完成后，检查哪个编号区域中有对象 - 再次填充该区域，0这次回来。
  • 洪水用 填充另一个编号的区域2，你就完成了。

这适用于任何网格配置，只要恰好有两个0扇区彼此断开即可；所以多次重新应用相同的算法就可以了。

编辑：小调整，为您节省一两个洪水填充 -

  • 如果您在第一次填充中没有找到您的对象，您可以假设另一个扇区有它，所以您只需重新填充当前数字2并让另一个扇区不理会（因为它已经被0填充了）。
  • 或者，如果您确实在第一次填充中找到了对象，您可以直接用 填充另一个扇区2，然后用 重新填充第一个扇区0。
于 2010-05-15T21:23:37.290 回答