algorithm - 扭曲网格中的最短路径

我试图解决一个基于图的问题，这是一个声明：
我必须找到从标记位置到标记位置的最短路线[注：我标记s和E只是为了便于理解]这里有一个问题，我只能通过标记为0的单元格，标记为1的单元格表示无法通过的墙此外，我可以选择remove only one wall如果它能给我一个更短的退出路线。只能在基本方向上移动；不允许对角移动。
二维网格示例：

[
    [0(S) 1  1  1  1   ],
    [0    0  1  1  1   ],
    [1    0  1  0  1   ],
    [1    1  0  0  0(E)],
]

如果没有拆除墙壁的选项，我可以简单地使用Bfs或Dijkstra来找到最短的路线。这里提出了这个问题：
here-他们简单地使用完全穷举搜索，这对大型矩阵非常不利，他们关注基于语言的优化，这不是解决问题的好方法。
Someone asked it here-接受的答案有以下方法：
从监狱门口开始进行一次全方位的搜查
每个可通行空间与监狱门的距离。
从逃生舱开始进行另一次广度优先搜索
每个可通行空间与逃生舱的距离。
现在遍历这些墙，并考虑依次移除每个墙。
你知道每个可通行的地方离监狱门的距离
还有逃生舱，你可以马上计算出
穿过墙壁留下的空间的最短路线
你刚搬走。
但我不清楚上面第三步的意思是什么（所以你可以立即计算出穿过墙壁留下的空间的最短路线的长度）。
还有没有更好的方法来接近它？
它能用动态规划而不使用图来解决吗？

最佳答案

我只需对图进行一些扩展，如下所示：构建一个新的图G'，它是初始图G的两倍大G'的每个节点表示一个状态(v, rem)，其中v是G的节点，rem \in {0, 1}表示您是否已经删除了一个节点另外添加一个新节点
G'中的相邻项如下：
所有(v, 0)s（分别(v, 1)s）在彼此之间链接，就像g中一样（如果它们都有值0）。
如果v1的值为0，而其中一个neihbors v2的值为1，则在(v1, 0)和(v2, 1)之间添加一条边。
(E, 0)和(E, 1)都与成本为0的E_new相关（如果不使用成本，只需在最后去掉1）。
你现在的目标是从(s, 0)到E_new，dijkstra（如果所有步骤的成本都相同，那么在你的情况下，bfs）应该可以在最短的时间内正常工作，其中n是你的节点数（而不是正方形的边）。A*的速度会更快，但实现起来要复杂一些如果希望在不移除墙的情况下获得解决方案（长度相等），则必须注意执行bfs的顺序（先执行rem=0的节点）。
这与（实际上是的）Shortest path in matrix with obstacles with cheat paths非常相似。
编辑：
上面提到的答案具有相同的复杂性，需要2个BFS，而不是1个，但在一个图上两个更小，所以可能类似，再加上另一个循环，所以我不知道哪个更快。
（所以你可以立即计算出
穿过墙壁留下的空间）
在步骤1和2中，你计算了源和每个墙之间的SORTEST路径，另一方面，在出口和所有墙之间，不经过任何墙。通过为给定的墙节点添加这两个值，可以获得从s到e仅穿过该墙的路径的长度通过遍历所有的墙（或者至少是其中的一部分，如果你做得很聪明的话），你得到了最短的路径，你可以在不穿过任何墙的情况下将其与最短的路径（s，e）进行比较，从而只保留最好的路径。
编辑2
下面是我的方法的一个小例子：
假设你的网格是这样的：

[[0, 0, 1],
 [0, 1, 0]]

其中的节点可以用它们的坐标（1，1），（1，2）等表示。
唯一存在的边是（1，1）到（1，2）和（1，1）到（2，1），以及（3，1）和（2，2）到（3，2）。向每个节点添加一个第3维rem，它可以接受值0或1。对于rem的每个值，如果（i1，j1）->（i2，j2）在图中，那么现在就有（i1，j1，rem）->（i2，j2，rem）对于图中没有的所有边（i1，j1）->（i2，j2）（因为墙），现在有了（i1，j1，0）->（i2，j2，1）加上，最后，（2，3，0）－>E_new和（2，3，1）－>E_new。你可以在这个新图表中运行BFS。

关于algorithm - 扭曲网格中的最短路径，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/43677348/