骑士巡游最短路径求解：DFS方案超时问题排查咨询

问题背景 #

给定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），无法得到正确结果。请问该问题的正确解法是什么？我的代码错误原因何在？

代码错误原因 #

• DFS不适合求最短路径：DFS会沿着一条路径走到头再回溯，会遍历大量无关路径，时间复杂度极高。哪怕是n=6的小棋盘，也会因为重复探索导致超时。
• 无记忆化优化：同一个位置会被多次递归计算，没有记录已经得到的最短步数，进一步浪费时间。
• 不可达标记不合理：用500作为不可达的阈值，如果实际路径长度超过500会误判，而且这个数值没有依据。

正确解法：BFS（广度优先搜索） #

求最短路径问题，BFS是最优方案——它按层遍历，第一次到达终点时的层数就是最少步数，不会做无用的深度探索。

BFS实现思路 #

1. 用队列存储当前位置和对应的移动步数
2. 用二维数组标记已访问的位置，避免重复处理
3. 每次从队列取出一个位置，遍历骑士的8种可能移动方向
4. 若移动后的位置合法且未访问，就加入队列，步数加1
5. 一旦到达终点，直接返回当前步数；若队列为空仍未找到终点，返回-1

示例代码 #

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

class Cell {
public:
    int x, y;
    Cell(int x, int y) : x(x), y(y) {}
};

// 骑士的8种移动方向
const int dx[] = {2, 2, -2, -2, 1, 1, -1, -1};
const int dy[] = {1, -1, 1, -1, 2, -2, 2, -2};

int minMovesRequired(int n, Cell start, Cell end) {
    // 转换为0索引（代码中数组从0开始）
    int startX = start.x - 1;
    int startY = start.y - 1;
    int endX = end.x - 1;
    int endY = end.y - 1;

    // 起点就是终点，直接返回0
    if (startX == endX && startY == endY) return 0;

    // 访问标记数组，避免重复处理同一个位置
    vector<vector<bool>> visited(n, vector<bool>(n, false));
    // 队列存储(坐标, 当前步数)
    queue<pair<pair<int, int>, int>> q;

    q.push({{startX, startY}, 0});
    visited[startX][startY] = true;

    while (!q.empty()) {
        auto current = q.front();
        q.pop();

        int x = current.first.first;
        int y = current.first.second;
        int steps = current.second;

        // 遍历所有8种移动方向
        for (int i = 0; i < 8; ++i) {
            int newX = x + dx[i];
            int newY = y + dy[i];

            // 到达终点，返回步数+1
            if (newX == endX && newY == endY) {
                return steps + 1;
            }

            // 检查位置是否在棋盘内且未被访问
            if (newX >= 0 && newX < n && newY >= 0 && newY < n && !visited[newX][newY]) {
                visited[newX][newY] = true;
                q.push({{newX, newY}, steps + 1});
            }
        }
    }

    // 队列为空，说明无法到达终点
    return -1;
}

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;
}

代码说明 #

• 队列实现层级遍历，每一层对应骑士移动的步数，保证第一次到达终点时的步数就是最小值
• 访问数组避免重复处理同一个位置，大幅提升效率
• 时间复杂度为O(n²)，空间复杂度O(n²)，对于n=6的场景完全无压力

内容的提问来源于stack exchange，提问作者new