algorithm - 如何检测添加 block 后永远不会成为最短路径一部分的网格上的正方形？

Question

我有一个带有起点、终点和一些墙的网格。单位采用最短路径(仅向上/向下/向左/向右移动)从起点到终点，不穿过墙壁。

用户可以根据需要添加任意数量的额外墙来更改路径。

但是，请注意，无论添加多少墙或在何处添加，都有一些方 block 永远不会成为最短路径的一部分!

这些方 block 永远不可能成为最短路径的一部分!

我正在寻找一种方法来检测哪些方 block 永远不会成为最短路径的一部分。

---

以上案例很容易找到；但还有更复杂的情况。考虑:

在上图中，没有一个带红点的方 block 是最佳路径的一部分，因为该区域只有一个入口，而且只有两个空格宽。如果它是三个空格宽，或者如果移除了任何一堵墙，那么这些方 block 中的大部分都可能成为最佳路径的一部分。

我一直在尝试找出一种方法来检测上述情况(主要使用最小剪切和洪水填充)，但没有成功。有谁知道解决这个问题的方法吗？

Answer 1

考虑从 S 到 F 的任何路径。该路径可能是最短路径(如果您删除所有其他方 block )除非您可以仅使用这些方 block 走“捷径”。只有当您有两个相邻的方 block 在路径中不相邻时才会发生这种情况。所以你需要考虑所有成对的相邻方 block ；他们与 S 或 F 断开连接的任何东西(没有断开 S 与 F 的连接)都不能成为最短路径的一部分。此外，可以通过单个正方形断开连接的图 block 不能成为从 S 到 F 的任何路径(不重复顶点)的一部分，因此它们也需要走。

令 N 为网格中的方 block 数。对于任何特定的一对正方形(它们有 O(N) 个)，可以在 O(N) 时间内使用 floodfill 计算断开连接的内容，因此这是 O(N^2)。这比你提到尝试过的 min-cut 便宜，所以我认为它对你来说足够便宜了。