1 条题解

  • 0
    @ 2026-2-17 22:07:56
    #include<bits/stdc++.h>
    using namespace std;
    
    // [1] 12种合法移动方向:前8个是马走日,后4个是象走田
    int dx[] = {1, 1, -1, -1, 2, 2, -2, -2, 2, 2, -2, -2};
    int dy[] = {2, -2, 2, -2, 1, -1, 1, -1, 2, -2, 2, -2};
    // [2] dist[x][y]:从(x,y)到(1,1)的最少步数
    int dist[105][105];
    // 棋盘大小为100×100,坐标范围1~100
    const int MAX_BOARD = 100;
    
    // [3] BFS预处理:从终点(1,1)出发,计算所有点的最少步数
    void bfs_preprocess()
    {
        // 初始化距离数组为-1,表示该点未被访问
        memset(dist, -1, sizeof(dist));
        // 队列存储待遍历的坐标
        queue<pair<int, int>> q;
        
        // 起点(1,1)的步数为0,入队启动BFS
        dist[1][1] = 0;
        q.push({1, 1});
    
        // 标准BFS循环,层级遍历所有可达点
        while(!q.empty())
        {
            // 取出队首的当前坐标
            auto cur = q.front();
            q.pop();
            int x = cur.first;
            int y = cur.second;
    
            // 遍历12种移动方向
            for(int i = 0; i < 12; i++)
            {
                // 计算移动后的新坐标
                int nx = x + dx[i];
                int ny = y + dy[i];
                // 合法性检查:坐标在棋盘内,且未被访问过
                if(nx >= 1 && nx <= MAX_BOARD && ny >= 1 && ny <= MAX_BOARD && dist[nx][ny] == -1)
                {
                    // 步数+1,标记已访问,新坐标入队
                    dist[nx][ny] = dist[x][y] + 1;
                    q.push({nx, ny});
                }
            }
        }
    }
    
    int main()
    {
        // [4] 预处理整个棋盘的最少步数,仅需执行一次
        bfs_preprocess();
    
        // [5] 读取两个马的坐标
        int x1, y1, x2, y2;
        cin >> x1 >> y1;
        cin >> x2 >> y2;
    
        // [6] 直接查表输出两个坐标的最少步数
        cout << dist[x1][y1] << endl;
        cout << dist[x2][y2] << endl;
    
        return 0;
    }
    
    • 1

    信息

    ID
    1308
    时间
    1000ms
    内存
    256MiB
    难度
    1
    标签
    递交数
    1
    已通过
    1
    上传者