- 题目链接：http://noi.openjudge.cn/ch0205/2753/
- 总时间限制: 1000ms 内存限制: 65536kB
- 描述
-
一个迷宫由R行C列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。
给定一个迷宫，求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走，不能斜着走。 - 输入
-
第一行是两个整数，Ｒ和Ｃ，代表迷宫的长和宽。（ 1<= R，C <= 40)
接下来是Ｒ行，每行Ｃ个字符，代表整个迷宫。
空地格子用'.'表示，有障碍物的格子用'#'表示。
迷宫左上角和右下角都是'.'。 - 输出
- 输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。
- 样例输入
-
5 5 ..### #.... #.#.# #.#.# #.#..
- 样例输出
-
9
算法分析：
迷宫问题的最短路径，广搜。
1 #include<stdio.h> 2 #include<iostream> 3 #include<queue> 4 using namespace std; 5 struct obj 6 { 7 int x,y,step;//step表示从出发点到达(i,j)需要的步数 . 8 }; 9 10 int R,C; 11 char map[42][42]; 12 queue<struct obj> q; 13 struct obj Start,End; 14 15 int dx[4]={-1,0,1,0};//上右下左 16 int dy[4]={0,1,0,-1}; 17 void BFS(); 18 19 int main(int argc, char *argv[]) 20 { 21 //freopen("2753.in","r",stdin); 22 int i,j; 23 char c; 24 25 scanf("%d%d",&R,&C);//getchar();//吸收回车 26 while ((c = getchar()) != EOF && c != '\n'); 27 //不停地使用getchar()获取缓冲中字符，直到获取的c是“\n”或文件结尾符EOF为止 28 for(i=0;i<R;i++) 29 { 30 gets(map[i]); 31 /* 32 for(j=0;j<C;j++) 33 { 34 map[i][j]=getchar(); 35 } 36 getchar();//吸收回车 37 */ 38 } 39 Start.x=0; 40 Start.y=0; 41 Start.step=1; 42 End.x=R-1; 43 End.y=C-1; 44 End.step=-1; 45 46 BFS(); 47 printf("%d\n",End.step); 48 49 return 0; 50 } 51 52 void BFS() 53 { 54 int i,txx,tyy; 55 struct obj temp; 56 57 /*while(!q.empty()) q.pop(); 58 if(Start.x==End.x&&Start.y==End.y) 59 { 60 End.step=1; 61 return ; 62 }*/ 63 q.push(Start); 64 while(!q.empty()) 65 { 66 for(i=0;i<4;i++) 67 { 68 txx=q.front().x+dx[i]; 69 tyy=q.front().y+dy[i]; 70 if(txx>=0&&txx<R&&tyy>=0&&tyy<C&&map[txx][tyy]=='.') 71 { 72 temp.x=txx; 73 temp.y=tyy; 74 temp.step=q.front().step+1; 75 q.push(temp); 76 map[txx][tyy]='#'; 77 if(txx==End.x&&tyy==End.y) 78 { 79 End.step=temp.step; 80 return ; 81 } 82 } 83 } 84 q.pop(); 85 } 86 }
