我有一个带有开始，结束和一些墙的网格 . 单位从开始到结束采用最短路径（仅向上/向下/向左/向右移动），而不穿过墙壁 .
允许用户添加他们想要更改路径的额外墙 .
但是，请注意，无论添加多少墙壁或添加了哪些墙壁，都有一些方块可以成为最短路径的一部分！
这些方块永远不会成为最短路径的一部分！
我正在寻找一种方法来检测哪些方块永远不会成为最短路径的一部分 .
以上案例很容易找到;但还有更复杂的案例 . 考虑：
在上图中，没有带红点的正方形可以成为最佳路径的一部分，因为该区域只有一个入口，并且它只有两个宽度 . 如果它是三个宽度的空间，或者如果任何一个墙被移除，那么大多数这些正方形可能是最佳路径的一部分 .
我一直试图找出一种方法来检测上述情况（主要是使用最小割和洪水填充），但没有成功 . 有谁知道解决这个问题的方法？
2 回答
考虑从S到F的任何路径 . 该路径可以是最短路径（如果您删除所有其他方块），除非您可以仅使用这些切片来获取“快捷方式” . 仅当您在路径中有两个相邻的正方形时才会发生这种情况 . 所以你需要考虑所有相邻的正方形对;他们与S或F断开连接的任何东西（不断开S与F的连接）都不能成为最短路径的一部分 . 此外，可以通过单个方块断开连接的切片不能是从S到F的任何路径（不重复顶点）的一部分，因此它们也需要也是如此 .
设N是网格中的平方数 . 对于任何特定的正方形对（其中有O（N）），可以在O（N）时间内使用填充来计算断开连接的内容，因此这是O（N ^ 2） . 哪个比你提到的最小切割便宜，所以我认为它足够便宜 .
首先我们看到， the areas can be blocked by one or two adjacent grids will never be in any shortest path .
在你的例子中看到的情况是，这两个黄色网格使点被阻挡 .
被一个网格阻挡很容易理解 . 被两个人阻止时：
如果不相邻，我们可能会增加额外的墙壁，使其成为唯一的路径，通过一个并从另一个路径出去，所以我们可能需要内部的 .
如果相邻，我们总是可以从一个直接到另一个，所以我们仍然不需要该区域内的网格 .
所以这里有算法：
枚举每个空网格
在墙上放了一堵墙并使用洪水填充来找到被阻挡的区域，它们是没用的 .
尝试在其四个相邻网格中的一个上放一堵墙（如果是空的），使用填充填充来找到被阻挡的区域，它们是没用的 .