首先，这是一个断言，我不是在寻找直接的答案，而是您想要的最佳解决方案的复杂性，正如您可能认为的那样。
这是矩阵中 2 点(开始和结束)之间的最短路径的已知问题，同时有障碍物。移动可接受的是向上，向下，向左和向右。假设在移动时，我携带sth，每次移动的成本是2。矩阵中有一些点(让我们将它们命名为 B 点)，我可以将这个 sth 留在一个 B 点并从另一个 B 点拾取它。在B点倾倒sth的成本是1，从B点捡起sth的成本又是1。 每当我在没有这个sth的情况下搬家时，我现在搬家的成本是1。 我认为解决方案是将矩阵转换为树并应用 BFS。但是，这在没有 B 点的情况下有效。
每当我考虑到 B 点复杂性时，都会遇到最坏的情况 N^2。 这是一个例子：
S - - -
- - - -
B - - B
- - O E
S = 开始 ， E = 结束 ， B = B 点下降 sth， O = 障碍物 所以我从 S 开始向下移动到 B 点(2*2=4 点)离开 sth 在 B 点(1 点)向右移动(2*1= 2 点)，拿起它(1 点)，向下移动 2 点 = 总共 10 点。
我的想法是构建每个 B 点都有节点的树，但是这将创建一个几乎 (V-1)*(V-1) 边的非常密集的循环图，它采用 N^2 边界中的算法只是为了创建图。 这是上述最坏的情况：
S b b b
b b b b
b b b b
b b b E
我认为另一种选择是首先计算没有 B 点的最短路径。 然后进行迭代，在每次迭代时： 首先在 S 上有 bfs 和最接近的 B 在 E 和最近的 B 上有 BFS 然后看看 B 之间是否有最接近 S 的路径和最接近 E 的 B 之间的路径。 如果有，那么我会看看路径是否小于带有障碍物的常规最短路径。 如果它更大，那么就没有最短路径(没有贪婪的测试)。 如果 2 B 点之间没有路径，请尝试第二个最接近 S 的路径，然后重试。 如果再次没有路径，则第二个最接近E和最接近S。 但是，在最坏的情况下，我无法计算出这种情况的复杂性，而且没有贪婪的测试来评估这一点。 任何关于计算复杂性甚至指出最佳复杂性解决方案(不是解决方案，而只是复杂性)的帮助将不胜感激
您的矩阵是图形的表示形式。没有作弊路径，很容易实现一个不错的BFS。实施作弊路径没什么大不了的。只需在第一个"层"之上添加与另一个"层"相同的矩阵即可。底层是"携带"，顶层是"不携带"。您只能在给定成本的 B 点处移动到另一层。这与具有第三维度的BFS相同。
每层有 n^2 个节点和 (n-1)^2 条边，此外还有最多 n^2 个 eges 连接这些层。那是 O(n^2)。
你可以用 (N， w) 标记的节点构建一个新图，其中 N 是原始图中的节点(所以是矩阵中的一个位置)，w=0 或 1 是你是否背负了重量。然后很容易在此图中添加所有可能的边
这个新图形的大小为 2*V，而不是 V^2(边的数量约为 4*V+数字(B))。
然后，您可以使用最短路径算法，例如Dijkstra的算法：复杂度O(E + V log(V))，在您的情况下为O(V log(V))。