我有一个带有开始、结束和一些墙壁的网格。单位从起点到终点采用最短路径（仅向上/向下/向左/向右移动），无需穿过墙壁。
用户可以添加任意数量的额外墙来更改路径。
但是，请注意，无论添加多少墙或添加它们的位置，都有一些正方形永远不会成为最短路径的一部分！
这些正方形永远不能成为最短路径的一部分！
我正在寻找一种方法来检测哪些正方形永远不会成为最短路径的一部分。
上述案例很容易找到；但还有更复杂的情况。考虑：
在上图中，没有一个带有红点的方块是最佳路径的一部分，因为该区域只有一个入口，而且只有两个空间宽。如果它是三个空间宽，或者如果任何一堵墙被移除，那么这些方块中的大部分都可能成为最佳路径的一部分。
我一直在尝试找出一种方法来检测上述情况（主要使用最小切割和洪水填充），但没有成功。有谁知道解决这个问题的方法？
考虑从 S 到 F 的任何路径。该路径可能是最短路径（如果您删除每隔一个正方形），除非您可以仅使用这些图块采取“捷径”。仅当您有两个在路径中不相邻的相邻方格时才会发生这种情况。所以你需要考虑所有相邻的正方形对；他们从 S 或 F 断开的任何东西（没有从 F 断开 S）都不能成为最短路径的一部分。此外，可以通过单个正方形断开的图块不能成为从 S 到 F 的任何路径（不重复顶点）的一部分，因此它们也需要去。
设 N 为网格中的方格数。对于任何特定的正方形对（其中有 O(N) 个），可以在 O(N) 时间内使用洪水填充计算断开的内容，因此这是 O(N^2)。这比你提到的尝试的 min-cut 便宜，所以我认为它对你来说足够便宜。
首先我们看到，可以被一个或两个相邻网格阻挡的区域永远不会在任何最短路径上。
请参阅您的示例中的情况，正是这两个黄色网格使点被阻塞。
被一格挡住很容易理解。当被两个人阻止时：
所以算法来了：
枚举每个空网格