侧边栏壁纸
博主头像
GabrielxD

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

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【BFS】乳草的入侵

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

题目

189. 乳草的入侵 - AcWing题库


农民约翰一直努力让他的草地充满鲜美多汁而又健康的牧草。

可惜天不从人愿,他在植物大战人类中败下阵来。

邪恶的乳草已经在他的农场的西北部份占领了一片立足之地。

草地像往常一样,被分割成一个高度为 YY ,宽度为 XX 的直角网格。

(1,1)(1,1) 是左下角的格(也就是说坐标排布跟一般的 X,YX,Y 坐标相同)。

乳草一开始占领了格 ( Mx,MyM_x,M_y )。

每个星期,乳草传播到已被乳草占领的格子四面八方的每一个没有很多石头的格(包括垂直与水平相邻的和对角线上相邻的格)内。

11 周之后,这些新占领的格又可以把乳草传播到更多的格里面了。

达达想要在草地被乳草完全占领之前尽可能的享用所有的牧草。

她很好奇到底乳草要多久才能占领整个草地。

如果乳草在 00 时刻处于格 ( Mx,MyM_x,M_y ),那么几个星期以后它们可以完全占领入侵整片草地呢(对给定的数据总是会发生)?

在草地地图中,. 表示草,而 * 表示大石。

比如这个 X=4,Y=3X=4, Y=3 的例子。

....
..*.
.**.

如果乳草一开始在左下角(第 11 排,第 11 列),那么草地的地图将会以如下态势发展:

      ....  ....  MMM.  MMMM  MMMM  
      ..*.  MM*.  MM*.  MM*M  MM*M  
      M**.  M**.  M**.  M**.  M**M  
星期数  0     1     2     3     4

乳草会在 44 星期后占领整片土地。

输入格式

11 行: 四个由空格隔开的整数: XX , YY , MxM_x , MyM_y

22 到第 Y+1Y+1 行: 每行包含一个由 XX 个字符(. 表示草地,* 表示大石)构成的字符串,共同描绘了草地的完整地图。

输出格式

输出一个整数,表示乳草完全占领草地所需要的星期数。

数据范围

1X,Y1001 \le X,Y \le 100

输入样例:

4 3 1 1
....
..*.
.**.

输出样例:

4

解题

方法一:BFS

思路

题本身不难,就是个BFS模板题,但输入数据给出的网格与坐标是用笛卡尔坐标系表示出来的,在输入的时候要把它转成一般的二维数组形式就顺时针旋转 90°90\degree(因为这个 WA55 次)。

代码

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

using namespace std;

typedef pair<int, int> PII;
typedef pair<PII, int> PIII;

const int N = 110, DIRS[][2] = {{-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}};
int X, Y, x, y;
bool g[N][N];

int main() {
    scanf("%d%d%d%d", &X, &Y, &x, &y);
    for (int i = Y; i >= 1; --i) {
        cin.ignore(numeric_limits<streamsize>::max(), '\n');
        for (int j = 1; j <= X; ++j) {
            char c;
            scanf("%c", &c);
            g[j][i] = c == '*';
        }
    }
    queue<PIII> que;
    que.push({{x, y}, 0});
    g[x][y] = true;
    int mx = 0;
    while (!que.empty()) {
        auto pr = que.front();
        que.pop();
        x = pr.first.first, y = pr.first.second;
        int step = pr.second;
        mx = max(mx, step);
        for (auto& DIR : DIRS) {
            int nx = x + DIR[0], ny = y + DIR[1];
            if (nx > 0 && nx <= X && ny > 0 && ny <= Y && !g[nx][ny]) {
                que.push({{nx, ny}, step + 1});
                g[nx][ny] = true;
            }
        }
    }
    printf("%d\n", mx);
    
    return 0;
}
0

评论区