AcWing 1099. 仙岛求药
宋标 Lv5
  2022-08-18 02:30:54 2022-08-18 02:30    

题目

少年李逍遥的婶婶病了，王小虎介绍他去一趟仙灵岛，向仙女姐姐要仙丹救婶婶。

叛逆但孝顺的李逍遥闯进了仙灵岛，克服了千险万难来到岛的中心，发现仙药摆在了迷阵的深处。

迷阵由M×N个方格组成，有的方格内有可以瞬秒李逍遥的怪物，而有的方格内则是安全。

现在李逍遥想尽快找到仙药，显然他应避开有怪物的方格，并经过最少的方格，而且那里会有神秘人物等待着他。

现在要求你来帮助他实现这个目标。

下图显示了一个迷阵的样例及李逍遥找到仙药的路线。

11.png

输入格式

输入有多组测试数据。

每组测试数据以两个非零整数 M 和 N 开始。M 表示迷阵行数, N 表示迷阵列数。

接下来有 M 行, 每行包含 N 个字符,不同字符分别代表不同含义:

  1. ‘@’：少年李逍遥所在的位置；
  2. ‘.’：可以安全通行的方格；
  3. ‘#’：有怪物的方格；
  4. ‘*’：仙药所在位置。

当在一行中读入的是两个零时，表示输入结束。

输出格式

对于每组测试数据，分别输出一行，该行包含李逍遥找到仙药需要穿过的最少的方格数目(计数包括初始位置的方块)。

如果他不可能找到仙药, 则输出 -1。

数据范围

输入样例：

8 8
.@##...#
#....#.#
#.#.##..
..#.###.
#.#...#.
..###.#.
...#.*..
.#...###
6 5
.*.#.
.#...
..##.
.....
.#...
....@
9 6
.#..#. 
.#.*.# 
.####. 
..#... 
..#... 
..#... 
..#... 
#.@.## 
.#..#. 
0 0

输出样例：

10
8
-1

题解

单源bfs
由于起点不固定，不然也可以用线性dp去做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstring>
#define N 310

using namespace std;

char g[N][N];
bool st[N][N];
int n, m;
int start;

int bfs()
{

    pair<int, int> q[N * N];
    int hh = 0, tt = 0;
    q[++ tt] = {start, 0};

    int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};

    while (tt > hh)
    {
        auto t = q[++ hh];
        int xy = t.first, dist = t.second;

        int x = xy / m, y = xy % m;
        for (int i = 0; i < 4; ++ i)
        {
            int a = x + dx[i], b = y + dy[i];
            if (a >= 0 && a < n && b >= 0 && b < m && !st[a][b] && g[a][b] != '#')
            {
                if (g[a][b] == '*') return dist + 1;
                st[a][b] = true;
                q[++ tt] = {a * m + b, dist + 1};
            }
        }
    }

    return -1;
}

int main()
{
    ios::sync_with_stdio(false);

    while (cin >> n >> m, n)
    {

        memset(st, false, sizeof st);

        for (int i = 0; i < n; ++ i)
            for (int j = 0; j < m; ++ j)
            {
                cin >> g[i][j];
                if (g[i][j] == '@') start = i * m + j, st[i][j] = true;
            }

        cout << bfs() << endl;
    }

    return 0;

}
 评论