当前位置：首页 > news >正文

【洛谷刷题】蓝桥杯专题突破-广度优先搜索-bfs（13）

news 2025/7/30 0:23:22

写在前面：

题目：P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输出格式：

输入样例：

输出样例：

解题思路：

代码：

AC ！！！！！！！！！！

写在最后：

写在前面：

怎么样才能学好一个算法？

我个人认为，系统性的刷题尤为重要，

所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，

事不宜迟，我们即刻开始刷题！

题目：P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题目描述：

输入格式：

输入只有一行四个整数，分别为n, m, x, y。

输出格式：

一个 n × m 的矩阵，代表马到达某个点最少要走几步（不能到达则输出 −1）。

输入样例：

3 3 1 1

输出样例：


输出 #1复制
0    3    2    
3    -1   1    
2    1    4

解题思路：

我们根据这道题的数据范围，可以判断出，

这道题需要使用广度优先搜索，题目要求是，

找出马到一个点最少需要几步，

我们用bfs，一层层搜索他的情况即可，

那么我们先来模拟一下题目给出的用例：

这个是我们的起点：

在象棋中，马走日字，在这个矩阵中，

它有两个位置可以走：

所以那两个位置被置为1，

表明马已经走了一步，

我们让马继续走：

马有走到这些位置，

继续记录路径和：

马继续走，以此类推，最后就会走到目标点位：

我们根据上面的规律实现代码，

但是这一次，我打算换一种方式，

因为调用STL库中的队列速度是比较慢的，

我们可以自己用数组模拟一个队列，

这样可以加快效率，

我们应该怎么实现呢？

我们可以用头尾两个指针维护这个队列，

往队列插入一个数：

如果要出队，那就让队头++，

这样就访问不了那个数了：

如果要入队，

就让队尾 tail++，再q[tail] = x。

如果队头大于队尾，那就证明队列为空：

下面是代码实现：

代码：

//包好头文件
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>using namespace std;int n, m, x, y;const int N = 500;//存坐标
typedef pair<int, int> PII;//存马的步数
int dist[N][N];//用数组模拟队列
PII q[N * N];//存坐标偏移量
int dx[] = {2, 2, 1, 1, -1, -1, -2, -2};
int dy[] = {1, -1, 2, -2, 2, -2, 1, -1};void bfs(int x, int y)
{//初始化memset(dist, -1, sizeof(dist));//插入第一个数据q[0] = {x, y};dist[x][y] = 0;int head = 0;int tail = 0;//如果头指针大于尾指针，证明队列为空while(head <= tail){auto t = q[head];head++;for(int i = 0; i < 8; i++){int a = dx[i] + t.first;int b = dy[i] + t.second;//控边界if(a < 1 || a > n || b < 1 || b > m) continue;if(dist[a][b] >= 0) continue;//记录马的步数dist[a][b] = dist[t.first][t.second] + 1;//入队tail++;q[tail] = {a, b};   }}
}int main()
{scanf("%d %d %d %d", &n, &m, &x, &y);bfs(x, y);for(int i = 1; i <= n; i++){for(int j = 1; j <= m; j++){printf("%-5d", dist[i][j]);}printf("\n");}return 0;
}