题目描述

给定一个 n∗n 的棋盘，以及一个开始位置和终点位置。

棋盘的横纵坐标范围都是 0∼n。

将一个国际象棋中的骑士放置在开始位置上，问将它移动至终点位置至少需要走多少步。

C++ 代码(BFS)

#include <iostream>
#include <cstring>
#include <queue>

using namespace std;

typedef pair<int, int> PII;
const int N = 310;
int dist[N][N];
bool st[N][N];
int sx, sy, ex, ey;
int n, t;

int bfs(){
    int dx[] = {-2, -1, 1, 2, -2, -1, 1, 2};
    int dy[] = {1, 2, 2, 1, -1, -2, -2, -1};
    queue<PII> q;

    // 初始化起点
    q.push({sx, sy});
    dist[sx][sy] = 0;
    st[sx][sy] = true;

    while(q.size()){
        PII t = q.front();
        q.pop();

        int x = t.first, y = t.second;

        for(int i = 0; i < 8; i ++){
            int px = x + dx[i], py = y + dy[i];

            // 边界判定
            if(px < 0 || px >= n || py < 0 || py >= n || st[px][py]) continue;
            if(dist[px][py] > dist[x][y] + 1){
                dist[px][py] = dist[x][y] + 1;
                q.push({px, py});
                st[px][py] = true;
            }
        }
    }
    return dist[ex][ey];
}

int main(void){
    scanf("%d", &t);
    while(t --){
        memset(dist, 0x3f, sizeof dist);
        memset(st, false, sizeof st);

        scanf("%d%d%d%d%d", &n, &sx, &sy, &ex, &ey);
        printf("%d\n", bfs());
    }
    return 0;
}