首页 > 代码库 > Openjudge 2.5 6264:走出迷宫
Openjudge 2.5 6264:走出迷宫
- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸,请你找出从起点到出口的最短路。- 输入
- 第一行是两个整数n和m(1<=n,m<=100),表示迷宫的行数和列数。
接下来n行,每行一个长为m的字符串,表示整个迷宫的布局。字符‘.‘表示空地,‘#‘表示墙,‘S‘表示起点,‘T‘表示出口。 - 输出
- 输出从起点到出口最少需要走的步数。
- 样例输入
3 3S#T.#....
- 样例输出
6
bfs
屠龙宝刀点击就送#include <iostream>#include <cstdlib>using namespace std;int ax[4]={0,0,1,-1},ay[4]={1,-1,0,0},a,b,c,d,i,j,n,m;char mg[101][101];int print(int p){ cout<<p<<endl; exit(0);}int ss(){ int head=0,tail=1,x,y,f[100*100][4]; f[tail][1]=a; f[tail][2]=b; f[tail][3]=1; mg[a][b]=‘#‘; do{ head++; for(i=0;i<4;++i) { x=f[head][1]+ax[i];y=f[head][2]+ay[i]; if(x>=0&&x<m&&y>=0&&y<n&&mg[x][y]==‘.‘) { tail++; f[tail][1]=x; f[tail][2]=y; f[tail][3]=f[head][3]+1; mg[x][y]=‘#‘; if(x==c&&y==d) { print(f[head][3]); break; } } } }while(head<tail);}int main(){ cin>>n>>m; for(i=0;i<n;++i) { for(j=0;j<m;++j) { cin>>mg[i][j]; if(mg[i][j]==‘S‘) { a=i; b=j; mg[i][j]=‘.‘; } if(mg[i][j]==‘T‘) { c=i; d=j; mg[i][j]=‘.‘; } } } ss(); return 0;}
Openjudge 2.5 6264:走出迷宫
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。