算法：确定由任意路径描绘的两个扇形的形状，然后填充其中一个

Question

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

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

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

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

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

一旦算法完成并且空的“扇区”被2完全填充，SAME算法必须足以再次执行相同的过程。第二次（以及后续），路径仍然是从 2 到不同的 2 绘制的，跨越 0 的空间，但是“ grid" 较小，因为被其他 2 包围的 2 无法被路径触及（因为路径沿着 0 的空间>）。

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

Answer 1

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

• 首先扫描数组找到 0，然后从那里开始洪水填充，用其他数字填充 0 区域，比方说 3 - 这将标记您的“部门”之一。
• 完成后，再次扫描 0，然后从那里进行洪水填充，这次填充 4。
• 在两次填充期间，您可以检查是否找到了对象；无论您在哪个填充过程中找到它，请记录该数字。
• 两次填充完成后，检查哪个编号区域中有对象 - 再次淹没该区域，这次返回 0。
• 用 2 填充其他编号区域，就完成了。

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

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

• 如果您在第一个洪水填充中没有找到您的对象，您可以假设其他部分有它，所以您只需用 2 重新填充当前数字，并保留其他扇区（因为它已经填充了 0）。
• 或者，如果您确实在第一个洪水填充中找到了对象，则可以直接用2填充另一个扇区，然后用重新填充第一个扇区>0。