ZSC 1306: 沼跃鱼早已看穿了一切题解

Time Limit: 1 Sec Memory Limit: 128 MB

题目链接： http://acm.two.moe:808/JudgeOnline/problem.php?id=1306

Description

沼跃鱼打开密码门后发现门后是一个像迷宫一样的房间，墙上的指示牌写着：房间内某处有一宝箱，但是宝箱被上锁了，钥匙在这个房间的某个角落。沼泽鱼对宝箱里有什么很感兴趣，但它必须先去拿到钥匙才可以打开宝箱。然而沼跃鱼早已看穿了一切，它看清了这个房间的布局，现在给出房间的布局图，问沼跃鱼拿到钥匙并打开宝箱最少需要走多少步。沼跃鱼每次只能向上、下、左、右中其中一个方向走一步，但若那个位置是墙时则不能往那个位置走（显然，沼跃鱼不能穿墙）。

Input

输入的第一行是一个整数T(0<T<20),代表接下来有T组数据。

每组数据的第一行有两个整数n,m(0<n,m≤10)，n代表房间的宽度，m代表房间的长度。

接下来n行，每行有m个字符，‘S’表示开始时沼跃鱼所处的位置，‘#’代表墙，‘*’代表空地，‘K’代表钥匙，‘B’表示宝箱。钥匙只有一把。

详情参看样例输入。

Output

对于每组数据，输出一行包含一个整数x，x代表沼跃鱼拿到钥匙并打开宝箱所需的最少步数。若沼跃鱼不能够拿到钥匙并打开宝箱（即到达不了钥匙或宝箱所在处）则输出-1。

Sample Input

5 6

***#B#

S**#*#

##***#

K#*#*#

***#*#

Sample Output

HINT

对于样例数据，房间宽5个单位，长6个单位。

从S出发到K需要的最少步数为8，而从K出发到B所需的最少步数为9.

所以答案为8 + 9 = 17.

请使用scanf("%s", s);或cin>> s;来读取字符串以避免出现漏读多读的情况。

Source

“美图杯”第二届新生赛，Author：13凌嘉威

题解: 一道相对容易的BFS（广度优先搜索）的题目，找到 S, K, B 的位置后按 S -> K , K -> B 的方向BFS，用 vis记录每一个可行的位置到起点的距离，就可以求出 S -> K -> B 的距离了，要注意是否可到达这一条件。

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <deque>
 4 #define INF 2147483647
 5  
 6 const int MAX = 32;
 7 const int cx[] = { -1, 0, 1, 0 };
 8 const int cy[] = { 0, 1, 0, -1 };
 9 char arr[MAX][MAX];
10 int vis[MAX][MAX];
11  
12 struct POINT{
13     int x, y;
14 };
15  
16 int BFS(POINT a, POINT b)
17 {
18     POINT c, tmp;
19     memset(vis, 0, sizeof(vis));
20 
21     std::deque<POINT> qu;    // 建立队列
22     qu.clear();
23     qu.push_back(a);
24 
25     while (!qu.empty())
26     {
27         c = qu.front();        //    取出队头元素
28         qu.pop_front();        //    队头元素出队
29         for (int i = 0; i < 4; i++)        //    4个方向遍历
30         {
31             if ((arr[c.x + cx[i]][c.y + cy[i]] != '#') && !vis[c.x + cx[i]][c.y + cy[i]])
32             {
33                 vis[c.x + cx[i]][c.y + cy[i]] = vis[c.x][c.y] + 1;
34                 tmp.x = c.x + cx[i]; tmp.y = c.y + cy[i];
35                 qu.push_back(tmp);
36             }
37         }
38     }
39     if (vis[b.x][b.y])        //    若可以到达，则返回到该点的距离
40         return vis[b.x][b.y];
41     return -INF;            //    否则返回一个不存在的值
42 }
43  
44 int main()
45 {
46 #ifdef CDZSC_OFFLINE
47     freopen("in.txt", "r", stdin);
48     freopen("out.txt", "w", stdout);
49 #endif
50     int t, n, m, t1, t2;
51     POINT a, b, c;
52     scanf("%d", &t);
53     while (t--)
54     {
55         scanf("%d%d", &n, &m);
56         memset(arr, '#', sizeof(arr));
57         for (int i = 1; i <= n; i++)
58         {
59             scanf("%s", arr[i] + 1);
60             arr[i][m + 1] = '#';
61         }
62         for (int i = 1; i <= n; i++)        // 寻找起点，钥匙位置，宝箱位置
63         {
64             for (int j = 1; j <= m; j++)
65             {
66                 if (arr[i][j] == 'S')
67                 {
68                     a.x = i; a.y = j;
69                 }
70                 else if (arr[i][j] == 'K')
71                 {
72                     b.x = i; b.y = j;
73                 }
74                 else if (arr[i][j] == 'B')
75                 {
76                     c.x = i; c.y = j;
77                 }
78             }
79         }
80         if (((t1 = BFS(a, b)) != -INF) && ((t2 = BFS(b, c)) != -INF))
81         {
82             printf("%d\n", t1 + t2);
83         }
84         else
85         {
86             printf("-1\n");
87         }
88     }
89     return 0;
90 }