bfs特殊方向
发布日期:2021-06-29 11:10:42
浏览次数:2
分类:技术文章
本文共 2787 字,大约阅读时间需要 9 分钟。
hdu1548;
题目链接;; 题目大意;电梯问题;只有两个方向;上下; hdu1372 题目链接;; 题目大意;象棋里面马走向的问题;方向就是马走日的方位;例如1548;
电梯;每层楼都有一个值;这个值就是在这层楼可以通过电梯上这么多层或者下这么多层;问从a层是否可以到达b层; 套用模板就是把for循环改成两个if而已;mark[now.x] = 1; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); if(now.x==b)//判断放前面;防止a==b的情况; { return now.step; } next.x=now.x-mp[now.x]; if(next.x>=1&&next.x<=n&&mark[next.x]==0) { mark[next.x] = 1; next.step = now.step+1; q.push(next); } next.x=now.x+mp[now.x]; if(next.x>=1&&next.x<=n&&mark[next.x]==0) { mark[next.x] = 1; next.step = now.step+1; q.push(next); } } return -1;
列如;1372;
就是简单的套模板就是把方向改变一下;在纸上模拟一下马日的走向;;;int dir[8][2]={ {-2,-1},{-1,-2},{1,-2},{2,-1},{2,1},{1,2},{-1,2},{-2,1}};
代码;
#include#include #include #include #include #include #include #include #include using namespace std;//两种移动方式;//之前把没有考虑a==b的情况一直wa;int n, a, b,bs;int mp[205];int mark[205];struct node{ int x,step;};int bfs(){ queue q; node now,next; memset(mark,0,sizeof(mark)); now.x = a;now.step=0; mark[now.x] = 1; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); if(now.x==b)//判断放前面;防止a==b的情况; { return now.step; } next.x=now.x-mp[now.x]; if(next.x>=1&&next.x<=n&&mark[next.x]==0) { mark[next.x] = 1; next.step = now.step+1; q.push(next); } next.x=now.x+mp[now.x]; if(next.x>=1&&next.x<=n&&mark[next.x]==0) { mark[next.x] = 1; next.step = now.step+1; q.push(next); } } return -1;}int main(){ int i; while(~scanf("%d",&n)&&n!=0) { scanf("%d %d",&a,&b); for(i = 1; i <= n; i++) { scanf("%d",&mp[i]); } printf("%d\n",bfs()); } return 0;}
第二道
#include#include #include #include #include #include #include #include #include using namespace std;//只是8个方向不同而已;没有限制条件;int s1,s2,e1,e2,bs;struct node{ int x,y,t;};int mark[10][10];int dir[8][2]={ {-2,-1},{-1,-2},{ 1,-2},{ 2,-1},{ 2,1},{ 1,2},{-1,2},{-2,1}};void bfs(){ int i; queue q; memset(mark,0,sizeof(mark)); node now, next; now.x=s1;now.y=s2;now.t=0; mark[now.x][now.y]=1; q.push(now); while(!q.empty()) { now = q.front(); q.pop(); if(now.x==e1&&now.y==e2) { bs = now.t; return ; } for(i = 0; i < 8; i++) { next.x = now.x+dir[i][0]; next.y = now.y+dir[i][1]; if(next.x>=1&&next.x<=8&&next.y>=1&&next.y<=8&&mark[next.x][next.y]==0) { mark[next.x][next.y] = 1; next.t = now.t+1; q.push(next); } } } return ;}int main(){ char a1 ,b1; int a2,b2; while(~scanf("%c%d %c%d",&a1,&a2,&b1,&b2)) { getchar(); s1 = a1-96;s2=a2; e1 = b1-96;e2=b2; bfs(); printf("To get from %c%d to %c%d takes %d knight moves.\n",a1,a2,b1,b2,bs); } return 0;}
转载地址:https://blog.csdn.net/zw1996/article/details/52225000 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年04月07日 01时18分13秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【视觉盛宴三】不好意思,这些线材接口的横截面真的没见过
2019-04-29
一位头发发白的神人教你怎么写程序,运维,买电脑,写文章,平面设计!
2019-04-29
【第二期】那些设计漂亮、有创意的电路板!
2019-04-29
【第三期】那些设计漂亮、有创意的电路板!
2019-04-29
继续推荐公众号~
2019-04-29
「第二篇」全国一等奖,经验帖。
2019-04-29
「第三篇」全国电子设计竞赛,这些你必须知道的比赛细节,文末附上近十年电赛题目下载...
2019-04-29
5G小科普(漫画版,So easy!)
2019-04-29
无人再提华强北
2019-04-29
千万不要小瞧那些不好好写代码的程序员
2019-04-29
80后,天才程序员, Facebook 第一任 CTO,看看开挂的人生到底有多变态?
2019-04-29
「第四篇」电赛控制题可以准备一些什么?
2019-04-29
「第五篇」全国电子设计竞赛-电源题设计方案总结
2019-04-29
「第六篇」对于电赛,我们应该看重什么?
2019-04-29
树莓派翻车了
2019-04-29
垃圾分类背后的数据和真相
2019-04-29
PID算法搞不懂?看这篇文章就够了。
2019-04-29
这位电子工程师,你不能错过。
2019-04-29
十八般武艺教你如何解决问题
2019-04-29
「权威发布」2019年大学生电子设计竞赛,仪器设备和主要元器件清单
2019-04-29