C++实现骑士走棋盘最小步数代码触发段错误(SIGSEGV)排查

你的代码出现Segmentation Fault的核心原因是无限制递归导致栈溢出，具体问题如下：

• 没有访问标记：你写的纯DFS递归没有记录已经走过的棋盘位置，骑士会在两个可达位置之间反复横跳（比如从A跳到B，下一步又从B跳回A），递归永远不会终止，调用栈深度会持续上涨直到超出系统分配的栈空间，直接触发内存访问错误。
• 逻辑本身存在缺陷：ans初始值设为-1，第一次到达目标点判断if(ans > cnt)时，负数永远小于非负的步数计数，就算递归能跑完，答案也永远不会被更新，返回值始终是-1。
• 算法选型错误：纯DFS不适合求无权最短路径，就算加了访问剪枝，也会优先沿单条路径走到头再回溯，棋盘尺寸稍大就会超时，这类最小步数问题最优解法是广度优先搜索（BFS），按层遍历第一次到达目标点的步数就是最小步数。

• 替换DFS为BFS实现，从起点开始逐层扩展骑士能走到的所有合法位置，每扩展一层步数+1，首次遇到目标坐标直接返回当前步数。
• 新增二维访问数组，标记已经入队遍历过的坐标，避免重复遍历和循环路径。
• 修正答案初始值逻辑，坐标判断严格遵循1基索引规则。

#include<bits/stdc++.h>
using namespace std;

class Solution 
{
    public:
    // 骑士8个移动方向
    int dx[8] = {2, 2, -1, 1, -2, -2, -1, 1};
    int dy[8] = {-1, 1, 2, 2, 1, -1, -2, -2};
    
    int minStepToReachTarget(vector<int>&KnightPos,vector<int>&TargetPos,int N)
    {
        // 起点和终点重合直接返回0
        if(KnightPos[0] == TargetPos[0] && KnightPos[1] == TargetPos[1]) return 0;
        vector<vector<bool>> vis(N+1, vector<bool>(N+1, false)); // 1基索引
        queue<pair<pair<int, int>, int>> q; // 存坐标和当前步数
        q.push({{KnightPos[0], KnightPos[1]}, 0});
        vis[KnightPos[0]][KnightPos[1]] = true;
        
        while(!q.empty()){
            auto cur = q.front();
            q.pop();
            int x = cur.first.first;
            int y = cur.first.second;
            int step = cur.second;
            
            for(int i=0; i<8; i++){
                int nx = x + dx[i];
                int ny = y + dy[i];
                if(nx == TargetPos[0] && ny == TargetPos[1]){
                    return step + 1;
                }
                if(nx >=1 && nx <=N && ny >=1 && ny <=N && !vis[nx][ny]){
                    vis[nx][ny] = true;
                    q.push({{nx, ny}, step+1});
                }
            }
        }
        return -1; // 题目保证可达，实际不会走到这
    }
};

int main(){
    int tc;
    cin >> tc;
    while(tc--){
        vector<int>KnightPos(2);
        vector<int>TargetPos(2);
        int N;
        cin >> N;
        cin >> KnightPos[0] >> KnightPos[1];
        cin >> TargetPos[0] >> TargetPos[1];
        Solution obj;
        int ans = obj.minStepToReachTarget(KnightPos, TargetPos, N);
        cout << ans <<"\n";
    }
    return 0;
}

针对你给出的测试用例，运行后输出结果为3，符合预期。

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