【BFS】移动骑士

题目

1102. 移动骑士

---

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

棋盘的横纵坐标范围都是 $0 \sim n-1$ 。

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

一个骑士在棋盘上可行的移动方式如下图所示：

输入格式

第一行包含整数 $T$ ，表示共有 $T$ 组测试数据。

每组测试数据第一行包含整数 $n$ ，表示棋盘大小。

第二行包含两个整数 $x,y$ 用来表示骑士的开始位置坐标 $(x,y)$ 。

第三行包含两个整数 $x,y$ 用来表示骑士的终点位置坐标 $(x,y)$ 。

输出格式

每组数据输出一个整数，表示骑士所需移动的最少步数，每个结果占一行。

数据范围

$4 \le n \le 300$ ,
$0 \le x,y \le n-1$

输入样例：

3
8
0 0
7 0
100
0 0
30 50
10
1 1
1 1

输出样例：

5
28
0

解题

方法一：BFS

思路

宽搜。

代码

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

using namespace std;

typedef pair<int, int> PII;

const int N = 310, DIRS[][2] = {{-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}, {-2, -1}};
int t, n;
int sx, sy, ex, ey;
bool vis[N][N];

int bfs() {
    memset(vis, 0, sizeof(vis));
    queue<PII> que;
    que.push({sx, sy});
    vis[sx][sy] = true;
    int step = 0;
    while (!que.empty()) {
        int sz = que.size();
        while (sz--) {
            auto curr = que.front();
            que.pop();
            int x = curr.first, y = curr.second;
            if (x == ex && y == ey) return step;
            for (auto& DIR : DIRS) {
                int nx = x + DIR[0], ny = y + DIR[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < n && !vis[nx][ny]) {
                    que.push({nx, ny});
                    vis[nx][ny] = true;
                }
            }
        }
        ++step;
    }
    return -1;
}

int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d%d%d%d%d", &n, &sx, &sy, &ex, &ey);
        printf("%d\n", bfs());
    }
    
    return 0;
}