使用单源最短路径遍历棋盘

Question

假设我们有一个n×n国际象棋棋盘(换句话说，就是一个矩阵)，每个方格都有一个权重。一块可以水平或垂直移动，但不能对角移动。每一次运动的费用等于棋盘上两个方格的差额。使用一种算法，我想要找到一个棋子从正方形(1,1)移动到平方(n，n)的最小代价，它在多项式时间中具有最坏的时间复杂度。

dikstras算法能解决这个问题吗？我下面的算法能解决这个问题吗？Diijkstras已经可以在多项式时间内运行，但是这一次的复杂性是什么呢？

伪码：

我们有一些空集S，一些整数V，并输入一个无权图。在此之后，我们完成了一个邻接矩阵，表示没有无限加权顶点的边的代价，而当矩阵没有选择所有的顶点时，我们找到一个顶点，如果平方值小于我们当前所处的平方，则移动到该方格，用两个平方之间的差更新V，并更新S标记被访问的每个顶点。我们这样做，直到没有更多的顶点。

谢谢。

Answer 1

由于您试图找到一个最小的成本路径，您可以使用Dijkstra的这一点。由于Dijkstra在最坏的情况下是O(|E| + |V|log|V|)，其中E是边数，V是图中的眩晕数，这满足了多项式时间复杂度的要求。

但是，如果您的算法只考虑与移动的开始和结束平方相关的成本，而不考虑中间节点，那么您必须将所有可能的开始和结束平方连接在一起，这样您就可以在中间节点周围采取“捷径”。