走出迷宫

题目链接：http://ica.openjudge.cn/dg3/3/

总时间限制: 1000ms 内存限制: 65536kB

描述

当你站在一个迷宫里的时候，往往会被错综复杂的道路弄得失去方向感，如果你能得到迷宫地图，事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸，请你找出从起点到出口的最短路。

输入

第一行是两个整数n和m(1<=n,m<=100)，表示迷宫的行数和列数。
接下来n行，每行一个长为m的字符串，表示整个迷宫的布局。字符'.'表示空地，'#'表示墙，'S'表示起点,'T'表示出口。

输出

输出从起点到出口最少需要走的步数。

样例输入

3 3
S#T
.#.
...

样例输出

分析：典型的广搜。注意提前把出发点和目的点的元素修改一下。

 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("
");
35     }
36     //printf("%d %d %d
",start.x,start.y,start.step);
37     //printf("%d %d %d
",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
",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
",destination.step);
67     return 0;
68 }