写在前面：
怎么样才能学好一个算法？
我个人认为，系统性的刷题尤为重要，
所以，为了学好广度优先搜索，为了用好搜索应对蓝桥杯，
事不宜迟，我们即刻开始刷题！
题目：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 #include #include #include using namespace std; int n, m, x, y; const int N = 500; //存坐标 typedef pair 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; }
AC ！！！！！！！！！！
写在最后：
以上就是本篇文章的内容了，感谢你的阅读。
如果喜欢本文的话，欢迎点赞和评论，写下你的见解。
如果想和我一起学习编程，不妨点个关注，我们一起学习，一同成长。
