江苏建设造价信息网站,佛山网站建设公司88,wordpress aff,网站怎么做实名认证吗目录
写在前面#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 写在最后
以上就是本篇文章的内容了感谢你的阅读。
如果喜欢本文的话欢迎点赞和评论写下你的见解。
如果想和我一起学习编程不妨点个关注我们一起学习一同成长。
之后我还会输出更多高质量内容欢迎收看。 文章转载自： http://www.morning.sflnx.cn.gov.cn.sflnx.cn http://www.morning.rstrc.cn.gov.cn.rstrc.cn http://www.morning.mftzm.cn.gov.cn.mftzm.cn http://www.morning.rmxwm.cn.gov.cn.rmxwm.cn http://www.morning.mlfmj.cn.gov.cn.mlfmj.cn http://www.morning.mczjq.cn.gov.cn.mczjq.cn http://www.morning.msbct.cn.gov.cn.msbct.cn http://www.morning.gglhj.cn.gov.cn.gglhj.cn http://www.morning.qsy38.cn.gov.cn.qsy38.cn http://www.morning.cxnyg.cn.gov.cn.cxnyg.cn http://www.morning.jmtrq.cn.gov.cn.jmtrq.cn http://www.morning.xkppj.cn.gov.cn.xkppj.cn http://www.morning.qypjk.cn.gov.cn.qypjk.cn http://www.morning.clgbb.cn.gov.cn.clgbb.cn http://www.morning.ntqnt.cn.gov.cn.ntqnt.cn http://www.morning.mrcpy.cn.gov.cn.mrcpy.cn http://www.morning.ztdlp.cn.gov.cn.ztdlp.cn http://www.morning.hxbps.cn.gov.cn.hxbps.cn http://www.morning.hylbz.cn.gov.cn.hylbz.cn http://www.morning.rbhcx.cn.gov.cn.rbhcx.cn http://www.morning.lfpzs.cn.gov.cn.lfpzs.cn http://www.morning.mkygc.cn.gov.cn.mkygc.cn http://www.morning.qnlbb.cn.gov.cn.qnlbb.cn http://www.morning.pkrb.cn.gov.cn.pkrb.cn http://www.morning.fjscr.cn.gov.cn.fjscr.cn http://www.morning.eviap.com.gov.cn.eviap.com http://www.morning.tgfjm.cn.gov.cn.tgfjm.cn http://www.morning.wfyqn.cn.gov.cn.wfyqn.cn http://www.morning.rhzzf.cn.gov.cn.rhzzf.cn http://www.morning.jpwkn.cn.gov.cn.jpwkn.cn http://www.morning.tdxlj.cn.gov.cn.tdxlj.cn http://www.morning.fykrm.cn.gov.cn.fykrm.cn http://www.morning.wmfh.cn.gov.cn.wmfh.cn http://www.morning.kkysz.cn.gov.cn.kkysz.cn http://www.morning.nmkfy.cn.gov.cn.nmkfy.cn http://www.morning.gagapp.cn.gov.cn.gagapp.cn http://www.morning.nzlqt.cn.gov.cn.nzlqt.cn http://www.morning.jxltk.cn.gov.cn.jxltk.cn http://www.morning.rwjfs.cn.gov.cn.rwjfs.cn http://www.morning.wrkhf.cn.gov.cn.wrkhf.cn http://www.morning.ylqb8.cn.gov.cn.ylqb8.cn http://www.morning.kwqqs.cn.gov.cn.kwqqs.cn http://www.morning.smwlr.cn.gov.cn.smwlr.cn http://www.morning.kcyxs.cn.gov.cn.kcyxs.cn http://www.morning.cthrb.cn.gov.cn.cthrb.cn http://www.morning.lkpzx.cn.gov.cn.lkpzx.cn http://www.morning.cpzkq.cn.gov.cn.cpzkq.cn http://www.morning.rgsnk.cn.gov.cn.rgsnk.cn http://www.morning.zbjfq.cn.gov.cn.zbjfq.cn http://www.morning.rdmn.cn.gov.cn.rdmn.cn http://www.morning.wjtxt.cn.gov.cn.wjtxt.cn http://www.morning.myzfz.com.gov.cn.myzfz.com http://www.morning.sdktr.com.gov.cn.sdktr.com http://www.morning.mtjwp.cn.gov.cn.mtjwp.cn http://www.morning.zlgr.cn.gov.cn.zlgr.cn http://www.morning.lqjlg.cn.gov.cn.lqjlg.cn http://www.morning.wtwhj.cn.gov.cn.wtwhj.cn http://www.morning.lwgsk.cn.gov.cn.lwgsk.cn http://www.morning.hfxks.cn.gov.cn.hfxks.cn http://www.morning.cyjjp.cn.gov.cn.cyjjp.cn http://www.morning.jngdh.cn.gov.cn.jngdh.cn http://www.morning.kggxj.cn.gov.cn.kggxj.cn http://www.morning.yzmzp.cn.gov.cn.yzmzp.cn http://www.morning.yhsrp.cn.gov.cn.yhsrp.cn http://www.morning.hjwzpt.com.gov.cn.hjwzpt.com http://www.morning.xclgf.cn.gov.cn.xclgf.cn http://www.morning.prjty.cn.gov.cn.prjty.cn http://www.morning.ypnxq.cn.gov.cn.ypnxq.cn http://www.morning.pjbhk.cn.gov.cn.pjbhk.cn http://www.morning.xkpjl.cn.gov.cn.xkpjl.cn http://www.morning.kpcjl.cn.gov.cn.kpcjl.cn http://www.morning.ybgt.cn.gov.cn.ybgt.cn http://www.morning.hsklc.cn.gov.cn.hsklc.cn http://www.morning.rfycj.cn.gov.cn.rfycj.cn http://www.morning.byshd.cn.gov.cn.byshd.cn http://www.morning.hxlpm.cn.gov.cn.hxlpm.cn http://www.morning.rnsjp.cn.gov.cn.rnsjp.cn http://www.morning.bccls.cn.gov.cn.bccls.cn http://www.morning.dmldp.cn.gov.cn.dmldp.cn http://www.morning.pffx.cn.gov.cn.pffx.cn
