codevs——3344 迷宫
2024-09-08 09:46:49
题目描述 Description
小刚在迷宫内,他需要从A点出发,按顺序经过B,C,D……,到达最后一个点,再回到A点。迷宫内有些障碍,问至少走几步。
输入描述 Input Description
第一行有三个数n,m表示迷宫有n行,m列。
第2行到第n+1行,每行m个字符,可能是’A’..’Z’,’2’,’0’ 其中,2表示障碍,0表示可以走。’A’..’Z’也可以走。
输出描述 Output Description
至少走几步可以按规定走完,如果不行,输出“Impossible”
样例输入 Sample Input
5 5
A002B
022C0
000D0
00222
0000E
样例输出 Sample Output
26
数据范围及提示 Data Size & Hint
0%的数据满足:1<=n<=10 1<=m<=10 字母为“A”..“B”。
30%的数据满足:1<=n<=10 1<=m<=10 字母为“A”..“G”。
50%的数据满足:1<=n<=10 1<=m<=10 字母为“A”..“Z”。
10%的数据满足:1<=n<=100 1<=m<=100 字母为“A”..“B”。
30%的数据满足:1<=n<=100 1<=m<=100 字母为“A”..“G”。
100%的数据满足:1<=n<=100 1<=m<=100 字母为“A”..“Z”。
bfs
以A为起点以B为终点,以B为起点以C为终点、、、以此类推,跑sum遍bfs找出每一个点到它下一个点的最小值,然后累加就可以了。
不要忘了判断没有路的情况
#include<queue> #include<cstdio> #include<cstring> #include<cstdlib> #include<iostream> #include<algorithm> #define N 210 using namespace std; char ch; bool flag; int dis[N][N],map[N][N]; int n,m,sx,sy,ex,ey,sum,ans; ]={,,,-},yy[]={,-,,}; int read() { ,f=; char ch=getchar(); ') ch=getchar(); +ch-'; ch=getchar();} return x*f; } struct Node { int x,y; }node[],que; queue<Node>q; void bfs(int sx,int sy) { while(!q.empty()) q.pop(); memset(dis,0x3f3f3f3f,sizeof(dis)); dis[sx][sy]=; que.x=sx,que.y=sy,q.push(que); while(!q.empty()) { Node p=q.front();q.pop(); if(p.x==ex&&p.y==ey) {ans+=dis[ex][ey]; return ;} ;i<;i++) { int fx=p.x+xx[i],fy=p.y+yy[i]; ||fy<||fx>n||fy>m||!map[fx][fy]) continue; ) continue; dis[fx][fy]=dis[p.x][p.y]+; que.x=fx,que.y=fy; q.push(que); } } flag=true; } int main() { n=read(),m=read(); ;i<=n;i++) ;j<=m;j++) { cin>>ch; ; ; if(ch>='A'&&ch<='Z') { sx=ch-; sum=max(sx,sum); node[sx].x=i; node[sx].y=j; } } ;i<=sum;i++) { sx=node[i].x,sy=node[i].y; if(i==sum) ex=node[].x,ey=node[].y; else ex=node[i+].x,ey=node[i+].y; bfs(sx,sy); } if(flag) printf("Impossible"); else printf("%d",ans); ; }
最新文章
- frame和bounds
- PHP最简单的后门,且难查,不报毒!
- <;<;Exceptional C++>;>; notes
- Debian deb源方法升级PHP软件包
- isArray polyfill
- `cocos2dx非完整` 开始自己的FW模块
- 小生经验贴 --- adapter的数据更新
- PHP中的urlencode和urldecode的理解
- Tornado基本使用
- c语言统计字符数(判断a-z哪个字符出现次数最多)
- centos ios镜像文件 安装详细
- 团队作业4——第一次项目冲刺(Alpha版本)第一天+第二天+第三天+第四天+第五天+第六天+第七天
- DNS查询相关
- 谈谈ISCSI\NAS\SAN及SAS之间的区别及优缺点--待补充
- 【机器学习】SKlearn + XGBoost 预测 Titanic 乘客幸存
- .Net转Java.08.format
- python写web服务器
- 1123.(重、错)Is It a Complete AVL Tree
- SharePoint 2013 workflows stop working (Failed on started.)
- 傻瓜式搭建php+nginx+mysql服务器环境