侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【BFS】移动骑士

GabrielxD
2022-12-20 / 0 评论 / 0 点赞 / 13 阅读 / 545 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-20,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1102. 移动骑士


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

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

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

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

QQ截图20191016061524.png

输入格式

第一行包含整数 TT ,表示共有 TT 组测试数据。

每组测试数据第一行包含整数 nn ,表示棋盘大小。

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

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

输出格式

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

数据范围

4n3004 \le n \le 300 ,
0x,yn10 \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;
}
0

评论区