Knight 的旅程解决方案给出了错误的输出？

Question

我们给出起点/终点和棋盘大小（n*n）的骑士旅程：

找出从起点到达终点的最少步数。 如果没有路径则返回-1:

我尝试用DFS解决它：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Cell {
public:
    int x, y;
    Cell(int x, int y) {
        this->x = x;
        this->y = y;
    }
};

int count(vector<vector<int>>& board, int a, int b, int x, int y, int n) {
    if (a >= n || b >= n || b < 0 || a < 0 || board[a][b] == 1) return 500;
    if (a == x && b == y) return 0;

    
    board[a][b] = 1;

    int one = count(board, a + 2, b + 1, x, y, n) + 1; 
    int two = count(board, a + 2, b - 1, x, y, n) + 1; 
    int three = count(board, a - 2, b + 1, x, y, n) + 1; 
    int four = count(board, a - 2, b - 1, x, y, n) + 1; 
    int five = count(board, a + 1, b + 2, x, y, n) + 1; 
    int six = count(board, a + 1, b - 2, x, y, n) + 1; 
    int seven = count(board, a - 1, b + 2, x, y, n) + 1; 
    int eight = count(board, a - 1, b - 2, x, y, n) + 1; 

    board[a][b] = 0;

    int minMoves = min({one, two, three, four, five, six, seven, eight});
    
    return minMoves;
}

int minMovesRequired(int n, Cell start, Cell end) {
    vector<vector<int>> board(n, vector<int>(n, 0));
    int a = start.x-1;
    int b = start.y-1;
    int c = end.x-1;
    int d = end.y-1;
    int ans = count(board, a, b, c, d, n);

    return (ans >= 500) ? -1 : ans;
}

int main() {
    int n = 6;
    Cell start(6, 1); 
    Cell end(2, 4); 

    int result = minMovesRequired(n, start, end);
    cout << "Minimum moves required: " << result << endl;

    return 0;
}

...但是对于这个输入：

n: 6 
start: 6, 1 
end: 2, 4

...我没有得到预期的输出：

• 预期输出：

  3

• 实际代码输出：

  tle

我应该如何解决这个问题？ 为什么这是错误的？

Answer 1

我没有得到预期的输出：预期输出：3，实际代码输出：tle

请注意，TLE 代表超出时间限制。这并不意味着您的代码最终不会输出正确的结果，而是它没有在分配的时间内达到该点。换句话说，你选择的算法效率不够。您的深度优先遍历将从源单元全面访问所有可能的路径。这将很快遇到数百万和数十亿条路径，对于相对较小的 𝑛 来说已经如此。

改进

广度优先遍历会对此有很大改善，因为棋盘有多大并不重要：如果存在长度为𝑘的最短路径，那么 BFS 将永远不会查找长于的路径𝑘.

另一个改进可能是使用 A* 算法：这种遍历可能有利于进入目标方向的路径，更快地找到目标。

但最有效的方法是观察当两个场相距较远时，有一个数学公式可以给你移动的次数。您可以分别处理两个字段接近且可能受到小板边界限制的情况。

识别公式和所有边界情况有点乏味，但这是一个很好的练习。

这是一个实现：

int minMovesRequired(int n, int ax, int ay, int bx, int by) {
    // Mirror in order to get A in the first quadrant of the board
    if (ax > n + 1 - ax) return minMovesRequired(n, n + 1 - ax, ay, n + 1 - bx, by); 
    if (ay > n + 1 - ay) return minMovesRequired(n, ax, n + 1 - ay, bx, n + 1 - by); 
    // Swap cells so A has the least X coordinate
    if (ax > bx) return minMovesRequired(n, bx, by, ax, ay); 
    int dx = bx - ax;
    int dy = abs(ay - by);
    // Mirror along diagonal to get that dx <= dy
    if (dx > dy) return minMovesRequired(n, ay, ax, by, bx);
    // Make the coordinates 0-based
    ax--;
    ay--;
    bx--;
    by--;
    int taxi = dx + dy;
    int odd = taxi % 2;
    // Identify different cases (like small boards and nearby cells):
    return taxi == 0 ? 0 // Trivial case
           // The center of a 3x3 board and All cells on a smaller board are isolated
         : n < 3 || n == 3 && ((ax & ay) == 1 || (bx & by) == 1) ? -1
           // An adjacent cell is reached in 3 steps
         : taxi == 1 ? 3
           // Distance 4: The two ends of the center column on 3x3; (0, 0)→(1, 1); and case on same diagonal:
         : n == 3 && dx == 0 && ax == 1 || dx == dy && dx < 3 && ((ax | ay) == 0 || dx == 2) ? 4
           // The two ends of the left column on 4x4 have distance 5:
         : n == 4 && (ax | bx) == 0 && dy == 3 ? 5
           // The two general cases:
         : dy < 2 * dx ? ((taxi + 4 - 3*odd) / 6) * 2 + odd
                       : ((  dy + 3 - 2*odd) / 4) * 2 + odd;
}

int main() {
    int n = 6;

    int result = minMovesRequired(n, 6, 1, 2, 4);
    cout << "Minimum moves required: " << result << endl;

    return 0;
}