- 总时间限制:
- 1000ms
- 内存限制:
- 65536kB
- 描述
-
当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸,请你找出从起点到出口的最短路。 - 输入
- 第一行是两个整数n和m(1<=n,m<=100),表示迷宫的行数和列数。
接下来n行,每行一个长为m的字符串,表示整个迷宫的布局。字符'.'表示空地,'#'表示墙,'S'表示起点,'T'表示出口。 - 输出
- 输出从起点到出口最少需要走的步数。
- 样例输入
-
3 3 S#T .#. ...
- 样例输出
- 6
- BFS,注意记录步数
1 #include<bits/stdc++.h>
2 using namespace std;
3 char a[505][505];
4 int mx[5]={0,-1,1,0,0};
5 int my[5]={0,0,0,-1,1};
6 int vis[505][505];
7 int N,M;
8 inline void ser();
9 int x,y;
10 int ANS=1e9;
11 queue<int> Qx,Qy,Qs;
12 int main(){
13 scanf("%d%d",&N,&M);
14 for(int i=1;i<=N;i++){
15 scanf("%s",a[i]+1);
16 for(int j=1;j<=M;j++){
17 if(a[i][j]=='S'){
18 x=i; y=j;
19 }
20 }
21 }
22 Qx.push(x); Qy.push(y), Qs.push(0);
23 vis[x][y]=1;
24 ser();
25 return 0;
26 }
27 inline void ser(){
28 while(Qx.size()!=0&&Qy.size()!=0){
29 int nowx=Qx.front();
30 int nowy=Qy.front();
31 int nows=Qs.front();
32 Qx.pop(); Qy.pop(); Qs.pop();
33 int tox,toy;
34 for(int i=1;i<=4;i++){
35 tox=nowx+mx[i];
36 toy=nowy+my[i];
37 if(vis[tox][toy]==0&&1<=tox&&tox<=N&&1<=toy&&toy<=M&&a[tox][toy]!='#'){
38 vis[tox][toy]=1;
39 if(a[tox][toy]=='T'){
40 cout<<nows+1<<endl;
41 exit(0);
42 }
43 else{
44 Qx.push(tox); Qy.push(toy); Qs.push(nows+1);
45 }
46 }
47 }
48 }
49 }
原文链接: https://www.cnblogs.com/CXCXCXC/p/4913062.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/223731
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!