仙岛求药（一）

仙岛求药（一）

难度级别：B；运行时间限制：1000ms；运行空间限制：256000KB；代码长度限制：2000000B

试题描述

少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。迷阵由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

题解

这是一道典型的dfs（电风扇），还有什么可以说？

代码如下

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 char map[101][101];
 5 int a[101][101],ans,m,n;
 6 int l=0;
 7 int c[101];
 8 void res(int u,int v,int i,int j)
 9 {
10     int t=a[u][v];
11     if(u==i&&v==j) ans=t;
12     t++;
13     if(v<m-1&&map[u][v+1]!='#'&&a[u][v+1]>t)        //判断四个方向是否可走。（可以走，就一只走到黑）dfs的重点 
14     {
15         a[u][v+1]=t;
16         res(u,v+1,i,j); 
17     }
18     if(u>0&&map[u-1][v]!='#'&&a[u-1][v]>t)
19     {
20         a[u-1][v]=t;
21         res(u-1,v,i,j);
22     }
23     if(v>0&&map[u][v-1]!='#'&&a[u][v-1]>t)
24     {
25         a[u][v-1]=t;
26         res(u,v-1,i,j);
27     }
28     if(u<n-1&&map[u+1][v]!='#'&&a[u+1][v]>t)
29     {
30         a[u+1][v]=t;
31         res(u+1,v,i,j);
32     }
33 }
34 int main() 
35 {
36     int startx,starty,endx,endy;
37     while(cin>>n>>m)     //试题说了不知道有几组数据，所以要判断。 
38     {
39         if((n==0)&&(m==0)) break;           //一样 
40         for(int i=0;i<n;i++)               //循环判断 
41           {
42             for(int j=0;j<m;j++)
43             {
44                 cin>>map[i][j];
45                 if(map[i][j]=='@')   //记录开始的地方 
46                 {
47                     startx=i;
48                     starty=j;
49                 }
50                 if(map[i][j]=='*')  //结束的地方 
51                 {
52                     endx=i;
53                     endy=j;
54                 }
55             }
56         }
57         memset(a,1,sizeof(a));     //memset的意思是赋值 
58         a[startx][starty]=0;      //设开始的地方访问过 
59         res(startx,starty,endx,endy); //开始递归 
60         if(ans!=0) c[l]=ans;    //判断是否可以走出 可以 
61         else c[l]=-1;          //不可以 
62         l++;        //计数用 
63         ans=0;   //清零 
64     }
65     for(int i=0;i<l;i++) cout<<c[i]<<endl;    //输出 
66 }

谢谢大家！