侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【BFS】仙岛求药

GabrielxD
2022-12-20 / 0 评论 / 0 点赞 / 18 阅读 / 717 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-12-20,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

1099. 仙岛求药


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

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

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

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

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

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

11.png

输入格式

输入有多组测试数据。

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

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

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

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

输出格式

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

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

数据范围

1N,M3001 \le N,M \le 300

输入样例:

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

输出样例:

10
8
-1

解题

方法一:BFS

思路

宽搜并记录步数。

代码

#include <iostream>
#include <limits>
#include <queue>

using namespace std;

typedef pair<int, int> PII;

const int N = 310, DIRS[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int n, m;
bool g[N][N];
int sx, sy, ex, ey;

int bfs() {
    queue<PII> que;
    que.push({sx, sy});
    g[sx][sy] = false;
    int step = 0;
    while (!que.empty()) {
        int sz = que.size();
        while (sz--) {
            auto curr = que.front();
            que.pop();
            int x = curr.first, y = curr.second;
            if (x == ex && y == ey) return step;
            for (auto& DIR : DIRS) {
                int nx = x + DIR[0], ny = y + DIR[1];
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && g[nx][ny]) {
                    que.push({nx, ny}); 
                    g[nx][ny] = false;
                }
            }
        }
        ++step;
    }
    return -1;
}

int main() {
    while (~scanf("%d%d", &n, &m) && n && m) {
        for (int i = 0; i < n; ++i) {
            cin.ignore(numeric_limits<streamsize>::max(), '\n');
            for (int j = 0; j < m; ++j) {
                char c;
                scanf("%c", &c);
                if (c == '@') sx = i, sy = j;
                else if (c == '*') ex = i, ey = j;
                g[i][j] = c != '#';
            }
        }
        printf("%d\n", bfs());
    }
    
    return 0;
}
0

评论区