没有炸弹的最小路径

Question

给出了大小为N x M的二维矩阵。每个单元格中的数据表示穿越该单元格的时间。一些区块包含表示炸弹的负值。我们需要找到不经过任何炸弹就从[0，0]到达[n-1，m-1]的最短时间。

• 我需要在这里做BFS还是在Dijkstra吗？如果我做BFS，它如何确定最短时间/最短时间？
• 如果我做Dijkstra，如何获得从[0，0]单元格到[n-1，m-1]的路径。

矩阵示例：

                        {0, 4, -1, -1, -1, -1, -1, 8, -1},
                        {4, 0, 8, -1, -1, -1, -1, 11, -1},
                        {-1, 8, 0, 7, -1, 4, -1, -1, 2},
                        {-1, -1, 7, 0, 9, 14, -1, -1, -1},
                        {-1, -1, -1, 9, 0, 10, -1, -1, 1},
                        {-1, -1, 4, -1, 10, 0, 2, -1, -1},
                        {-1, -1, -1, 14, -1, 2, 0, 1, 6},
                        {8, 11, -1, -1, -1, -1, 1, 0, 7},
                        {-1, -1, 2, -1, -1, -1, 6, 7, 0}

Answer 1

如果将二维矩阵做成图，那么每条边的遍历成本是相同的。在这种情况下，Djikstra 相当于 BFS。由于每个单元格的交叉成本不同，因此 Djikstra 并不等同于此处的 BFS。BFS 将确定需要穿过的最小单元数，但不会确定最短时间。所以这个要求是 Djiksta 的。这回答了您的第一个疑问。

我假设您知道如何实施 Djikstra 的。您面临的问题是如何在这个问题上实施它。为此，您需要将二维矩阵表示为图形。出现的主要问题是如何捕获图中节点值的关系。出现这种情况可能是因为您习惯于考虑边上的权重，而不是顶点上的权重。[i][k]然而，您可以简单地将问题简化为 Djikstra 问题，方法是使其成为有向图，其中从到 的边的成本为[j][k]的值[j][k]，向后方向的边的成本为 的值[i][k]。为了融入炸弹的概念，只需不要为这些单元生成顶点即可。之后，应用 Djikstra 的方法应该很简单。