- 题目链接：http://noi.openjudge.cn/ch0205/2727/
- 总时间限制: 1000ms 内存限制: 65536kB
- 描述
-
少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。现在要求你来帮助他实现这个目标。
下图 显示了一个迷阵的样例及李逍遥找到仙药的路线.
输入输入有多组测试数据. 每组测试数据以两个非零整数 M 和 N 开始，两者均不大于20。M 表示迷阵行数, N 表示迷阵列数。接下来有 M 行, 每行包含N个字符,不同字符分别代表不同含义:
1) ‘@’：少年李逍遥所在的位置；
2) ‘.’：可以安全通行的方格；
3) ‘#’：有怪物的方格；
4) ‘*’：仙药所在位置。
当在一行中读入的是两个零时，表示输入结束。
输出对于每组测试数据，分别输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。如果他不可能找到仙药, 则输出 -1。样例输入
8 8 .@##...# #....#.# #.#.##.. ..#.###. #.#...#. ..###.#. ...#.*.. .#...### 6 5 .*.#. .#... ..##. ..... .#... ....@ 9 6 .#..#. .#.*.# .####. ..#... ..#... ..#... ..#... #.@.## .#..#. 0 0
样例输出
10 8 -1
算法分析：
典型的迷宫最短路，广搜求解即可。注意搜索前把终点设置为可以到达，也就是设置为‘.’。
吐槽一下：现在好多人出题时给出的测试数据都是怎么了？一点都不遵守输出输出格式描述的格式，经常在这种字符数组题目的输入里面遇到坑。这道题下面这种输入方式就是不给过，输入的数据和预期输入的数据不一样。
想来想去，只好先读入二维数组再整体扫描二维数组了。
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 M,N; 11 char map[22][22]; 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("2727.in","r",stdin); 22 int i,j; 23 while(1) 24 { 25 scanf("%d%d",&M,&N);getchar();//吸收回车 26 if(M==0&&N==0) break; 27 //printf("%d %d\n",M,N); 28 for(i=0;i<M;i++) 29 { 30 gets(map[i]); 31 //puts(map[i]); 32 } 33 34 for(i=0;i<M;i++) 35 { 36 for(j=0;j<N;j++) 37 { 38 if(map[i][j]=='@') 39 { 40 Start.x=i; 41 Start.y=j; 42 Start.step=0;//起点步数是0. 43 } 44 else if(map[i][j]=='*') 45 { 46 End.x=i; 47 End.y=j; 48 End.step=-1;//找不到时，输出-1。所以默认是-1. 49 map[i][j]='.'; 50 } 51 } 52 } 53 54 BFS(); 55 printf("%d\n",End.step); 56 } 57 return 0; 58 } 59 60 void BFS() 61 { 62 int i,txx,tyy; 63 struct obj temp; 64 65 while(!q.empty()) q.pop(); 66 67 if(Start.x==End.x&&Start.y==End.y) 68 { 69 End.step=1; 70 return ; 71 } 72 q.push(Start); 73 while(!q.empty()) 74 { 75 for(i=0;i<4;i++) 76 { 77 txx=q.front().x+dx[i]; 78 tyy=q.front().y+dy[i]; 79 if(txx>=0&&txx<M&&tyy>=0&&tyy<N&&map[txx][tyy]=='.') 80 { 81 temp.x=txx; 82 temp.y=tyy; 83 temp.step=q.front().step+1; 84 q.push(temp); 85 map[txx][tyy]='#'; 86 if(txx==End.x&&tyy==End.y) 87 { 88 End.step=temp.step; 89 return ; 90 } 91 } 92 } 93 q.pop(); 94 } 95 }
查了一下资料：
https://zhidao.baidu.com/question/5241738.html
http://blog.csdn.net/guanyasu/article/details/53153705
找到一个比较靠谱的解决方案：
1 char c; 2 while ((c = getchar()) != EOF && c != '\n');//不停地使用getchar()获取缓冲中字符，直到获取的c是“\n”或文件结尾符EOF为止
于是上面的代码可以做如下改进：
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 M,N; 11 char map[22][22]; 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("2727.in","r",stdin); 22 int i,j; 23 char c; 24 while(1) 25 { 26 scanf("%d%d",&M,&N); 27 //printf("%d %d\n",M,N); 28 if(M==0&&N==0) break; 29 while((c=getchar()) != EOF && c != '\n');//不停地使用getchar()获取缓冲中字符，直到获取的c是“\n”或文件结尾符EOF为止 30 31 for(i=0;i<M;i++) 32 { 33 //gets(map[i]); 34 for(j=0;j<N;j++) 35 { 36 map[i][j]=getchar(); 37 //scanf("%c",&map[i][j]);//这个地方getchar()和scanf()都是可以的。 38 //printf("%c",map[i][j]); 39 if(map[i][j]=='@') 40 { 41 Start.x=i; 42 Start.y=j; 43 Start.step=0;//起点步数是0. 44 } 45 else if(map[i][j]=='*') 46 { 47 End.x=i; 48 End.y=j; 49 End.step=-1;//找不到时，输出-1。所以默认是-1. 50 map[i][j]='.'; 51 } 52 } 53 while((c=getchar()) != EOF && c != '\n');//不停地使用getchar()获取缓冲中字符，直到获取的c是“\n”或文件结尾符EOF为止 54 //printf("\n"); 55 } 56 57 BFS(); 58 printf("%d\n",End.step); 59 } 60 return 0; 61 } 62 63 void BFS() 64 { 65 int i,txx,tyy; 66 struct obj temp; 67 68 while(!q.empty()) q.pop(); 69 70 if(Start.x==End.x&&Start.y==End.y) 71 { 72 End.step=1; 73 return ; 74 } 75 q.push(Start); 76 while(!q.empty()) 77 { 78 for(i=0;i<4;i++) 79 { 80 txx=q.front().x+dx[i]; 81 tyy=q.front().y+dy[i]; 82 if(txx>=0&&txx<M&&tyy>=0&&tyy<N&&map[txx][tyy]=='.') 83 { 84 temp.x=txx; 85 temp.y=tyy; 86 temp.step=q.front().step+1; 87 q.push(temp); 88 map[txx][tyy]='#'; 89 if(txx==End.x&&tyy==End.y) 90 { 91 End.step=temp.step; 92 return ; 93 } 94 } 95 } 96 q.pop(); 97 } 98 }
