#1282. 走出迷宫
-
ID: 1282
传统题
1000ms
128MiB
尝试: 0
已通过: 0
难度: (无)
上传者:
走出迷宫
Description
当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。
#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
usingnamespacestd;
intn,m,vis[110][110];////用来标记有没有走过（有没有在队列中)
intdir[4][2]={{-1,0},{0,1},{1,0},{0,-1}};//定义方向 上右下左
chara[110][110];
structnode{
intr,c,step;//row ,column,step
};
voidbfs(intsr,intsc,inter,intec){
intk;
memset(vis,0,sizeof(vis));
queue<node> qe;//定义队列
node q,t;//q表示当前队头位置，t表示下一个位置
q.r=sr,q.c=sc,q.step=0;//把起点入队
vis[sr][sc]=1;//记录已经走过
qe.push(q);//入队
while(!qe.empty()){
q=qe.front();//取出队头元素
qe.pop();
if(er==q.r&&ec==q.c){//到出口了
printf("%d",q.step);
break;
}
for(k=0;k<4;k++){//继续搜索4个方向
t.r=q.r+dir[k][0],t.c=q.c+dir[k][1];
//如果没有出迷宫、并且该位置可走、没走过
if(0<=t.r&&t.r<n&&0<=t.c&&t.c<m&&vis[t.r][t.c]==0&&a[t.r][t.c]=='.'){
vis[t.r][t.c]=1;//走到这个位置
t.step=q.step+1;
qe.push(t);
}
}
}
}
intmain(){
inti,j,sr,sc,er,ec;
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)scanf("%s",a[i]);//读入字符数组 a[i]表示每行的首地址
for(i=0;i<n;i++)
for(j=0;j<m;j++)//求出入口和出口的位置
if(a[i][j]=='S')sr=i,sc=j;
elseif(a[i][j]=='T')er=i,ec=j,a[i][j]='.';
bfs(sr,sc,er,ec);//把出口和入口作为参数
return0;
}
Input Format
第一行是两个整数n和m(1≤n,m≤100)，表示迷宫的行数和列数。
接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符‘.’表示空地，‘#’表示墙，‘S’表示起点,‘T’表示出口。
Output Format
输出从起点到出口最少需要走的步数。
3 3
S#T
.#.
...6