江苏建设造价信息网站,平凉网站设计,怎样提高网站的排名,黑龙江 网站建设目录
写在前面#xff1a;
题目#xff1a;P1443 马的遍历 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 题目描述#xff1a; 输入格式#xff1a; 输出格式#xff1a; 输入样例#xff1a; 输出样例#xff1a;
解题思路#xff1a;
代码#xff1a;
AC
题目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 algorithmusing namespace std;int n, m, x, y;const int N 500;//存坐标
typedef pairint, 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;
}
AC 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。
