题目链接：http://ica.openjudge.cn/dg3/3/
- 总时间限制: 1000ms 内存限制: 65536kB
- 描述
-
当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。 - 输入
-
第一行是两个整数n和m(1<=n,m<=100)，表示迷宫的行数和列数。
接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符'.'表示空地，'#'表示墙，'S'表示起点,'T'表示出口。 - 输出
- 输出从起点到出口最少需要走的步数。
- 样例输入
-
3 3 S#T .#. ...
- 样例输出
-
6
分析：典型的广搜。注意提前把出发点和目的点的元素修改一下。
1 #include<stdio.h> 2 #include<queue> 3 #include<iostream> 4 using namespace std; 5 6 struct obj 7 { 8 int x,y; 9 int step;//表示从出发点到达（x，y）需要的步数 10 }; 11 12 char a[102][102]; 13 queue<struct obj> que; 14 struct obj start,destination; 15 int dx[4]={-1,0,1,0};//上右下左 16 int dy[4]={0,1,0,-1}; 17 18 int main(int argc, char *argv[]) 19 { 20 int n,m,i,j,xx,yy; 21 struct obj temp,temp2; 22 23 scanf("%d%d",&n,&m); 24 for(i=0;i<n;i++) 25 scanf("%s",a[i]); 26 for(i=0;i<n;i++) 27 { 28 for(j=0;j<m;j++) 29 { 30 if(a[i][j]=='S') { start.x=i; start.y=j; start.step=0; } 31 else if(a[i][j]=='T') { destination.x=i; destination.y=j; a[i][j]='.'; } 32 //printf("%c",a[i][j]); 33 } 34 //printf("\n"); 35 } 36 //printf("%d %d %d\n",start.x,start.y,start.step); 37 //printf("%d %d %d\n",destination.x,destination.y,destination.step); 38 39 a[start.x][start.y]='#'; 40 que.push(start); 41 while(!que.empty()) 42 { 43 temp=que.front();que.pop(); 44 //printf("%d %d %d ",temp.x,temp.y,temp.step); 45 //printf("%d %d %d\n",destination.x,destination.y,destination.step); 46 if(temp.x==destination.x&&temp.y==destination.y) 47 { 48 destination.step=temp.step; 49 break; 50 } 51 52 for(i=0;i<4;i++) 53 { 54 xx=temp.x+dx[i]; 55 yy=temp.y+dy[i]; 56 if(xx>=0&&xx<n&&yy>=0&&yy<m&&a[xx][yy]=='.') 57 { 58 a[xx][yy]='#'; 59 temp2.x=xx; 60 temp2.y=yy; 61 temp2.step=temp.step+1; 62 que.push(temp2); 63 } 64 } 65 } 66 printf("%d\n",destination.step); 67 return 0; 68 }
