top1编程
← 返回题目
题解

【基础】骑士巡游

1 条题解

  • 0
    @ 2026-7-28 22:09:22
    #include <bits/stdc++.h>
    using namespace std;
    
    int n,m;             // 棋盘的行数和列数
    int sx, sy;          // 初始位置坐标
    int ex, ey;          // 目标位置坐标
    int a[10][10];       // 棋盘数组,标记访问状态
    int fx[8]={-2, -1, 1, 2, 2, 1, -1, -2};  // 骑士的8个可能移动方向的x偏移量
    int fy[8]={1, 2, 2, 1, -1, -2, -2, -1};  // 骑士的8个可能移动方向的y偏移量
    int ans = INT_MAX;   // 记录最短路径长度,初始化为最大整数值
    
    /*
    算法思路:
    1) 使用fx和fy数组定义骑士的8个可能移动方向
    2) 使用深度优先搜索遍历所有可能路径
    3) 记录到达每个位置的最小步数
    4) 通过回溯确保每个位置只被访问一次
    */
    
    // 深度优先搜索函数
    // x, y: 当前位置坐标
    // cnt: 已走步数
    void dfs(int x, int y, int cnt){
        if(x == ex && y == ey){  // 到达目标位置
            ans = min(ans, cnt);  // 更新最短路径长度
            return; 
        }
        
        a[x][y] = 1;  // 标记当前位置为已访问
        
        // 尝试8个可能的移动方向
        for(int i=0;i<8;i++){
            int tx = x + fx[i];  // 计算新位置的x坐标
            int ty = y + fy[i];  // 计算新位置的y坐标
            
            // 检查新位置是否合法且未被访问过
            if(tx >= 1 && tx <= n && ty >= 1 && ty <= m && a[tx][ty] == 0){
                dfs(tx, ty, cnt+1);  // 递归搜索
                a[tx][ty] = 0;       // 回溯:撤销标记,允许其他路径访问
            }
        }
    }
    
    int main()
    {
        cin >> n >> m >> sx >> sy >> ex >> ey;  // 输入棋盘大小和起止位置
        dfs(sx, sy, 0);  // 从初始位置开始搜索,初始步数为0
        cout << ans;     // 输出最短路径长度
        return 0;
    }
    
    • 1