算法:确定由任意路径划定的两个扇区的形状，然后填充一个

Question

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

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

然后考虑相邻(水平或垂直)网格空间的任意路径。路径从 2 开始，到另一个 2 结束。路径上的每个空格都是 1。

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

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

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

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

Answer 1

在我看来是基本的flood fill算法将完成工作:

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

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

编辑: 细微调整，为您节省一两次洪水填充 -

• 如果在第一个flood-fill中没有找到你的对象，你可以假设其他扇区有它，所以你只需用2重新填充当前数字并留下另一个单独的扇区(因为它已经被 0 填充)。
• 或者，如果您确实找到了第一个flood-fill中的对象，您可以直接用2填充另一个扇区，然后重新填充第一个扇区与 0。