网格上具有阻塞单元和移动单元的最短路径

Question

我正在尝试解决从开始到结束在网格上移动对象的问题。我很清楚A *寻路算法，但是对于如何修改它却一无所知，因此它可以解决我的问题：

我有一个WxH网格。我需要将星形框移动到空框位置（它们始终处于相同位置：1,1和W-1，H-1）。我的出发点是空的（W-1，H-1），我迈出的每一步都是非对角的。如果我向上移动，则需要将阻碍自己前进的盒子向下移动到空白处，依此类推，直到到达恒星（1,1），然后我需要以相同的方式向起点移动。为了使事情变得更容易，恒星的运动总是朝着起点的方向进行，并且永远不会偏离起点。我需要找到最短的路线，也就是将星移到起始位置所需的最短步骤。

这里是一个2x2的网格来说明问题：

这显然是最短路径问题（也许是A *），但是我无法弄清楚这里需要的修改。我不是在寻找解决方案或答案，而只是在寻找方向，因为我对应该从哪里开始感到迷茫。

P.S。网格也可能有不动的盒子，但是一旦我理解了问题本身的算法，我就可以解决这个问题。

我正在尝试解决从开始到结束在网格上移动对象的问题。我很了解A *寻路算法，但是对于如何修改它，让它处理我的...我有点头绪。

Answer 1

[我不是在寻找解决方案或答案，只是在寻找方向，因为我对应该从哪里开始有点迷茫。