第十一届蓝桥杯省模拟赛——长草

第十一届蓝桥杯省模拟赛——长草

题目描述

小明有一块空地，他将这块空地划分为 $n$ 行 $m$ 列的小块，每行和每列的长度都为 $1$。

小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。

这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，则它将向自己的上、下、左、右四小块空地扩展，

这四小块空地都将变为有草的小块。请告诉小明，$k$ 个月后空地上哪些地方有草。

输入格式

输入的第一行包含两个整数 $n,m$。

接下来 $n$ 行，每行包含 $m$ 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 $g$，表示种了草。

接下来包含一个整数 $k$。 其中，$2\le n,m\le 1000，1\le k\le 10002\le n,m\le 1000，1\le k\le 1000$。

输出格式

输出 $n$ 行，每行包含 $m$ 个字母，表示 kk 个月后空地的状态。如果为小数点，表示为空地，如果字母为 $g$，表示长了草。

输入样例：

4 5
.g...
.....
..g..
.....
2
1
2
3
4
5
6

输出样例：

gggg.
gggg.
ggggg
.ggg.
1
2
3
4

运行限制

最大运行时间：1s
最大运行内存: 256M

题目大意

当在第$k$次迭代时，输出地图。
草只能向四周(上、下、左、右)扩散。
下图为模拟的样例：

题目解决思路

1. 将地图存储到g[N][N]，如果该点为草的话就将其入队列，迭代次数为0。

for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            char c;
            cin >> c;
            //如果此时的坐标是草,则加入到队列中去,迭代次数为0
            if(c == 'g') q[ ++ tt] = {i, j, 0};
            g[i][j] = c;
        }
    }
1
2
3
4
5
6
7
8
9
10
11

2. 利用bfs对地图上所有的不是草的点进行爆搜，在规定的最大迭代次数的情况下，将所有空地变为草。

void bfs()
{
    while (hh <= tt)//当队列中无元素时,推出循环
    {
        auto t = q[hh ++ ];//出队列
        int a = t.x, b = t.y, s = t.s;//取出点的坐标及其迭代次数
        if(s == k) break;//如果该点的迭代次数等于最大迭代次数,bfs结束
        for (int i = 0; i < 4; i ++ )//枚举四个向量
        {
            int x = a + dx[i], y = b + dy[i];
            //如果加了偏移量的点并没有越界且还是空地的话,就把空地变为草
            if(x >= 1 && y >= 1 && x <= n && y <= m && g[x][y] == '.')
            {
                g[x][y] = 'g';//空地变为草
                q[ ++ tt] = {x, y, s + 1};//将该点入队列,迭代次数加1
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

代码如下~

c++代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1010;

struct Edge
{
    int x, y, s;
} q[N * N];//x,y:点的坐标,s:迭代次数

char g[N][N];//地图
int hh, tt;//hh:队头,tt:队尾
int n, m;
int k;//最大迭代次数
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//四个向量代表上下左右

void bfs()
{
    while (hh <= tt)//当队列中无元素时,推出循环
    {
        auto t = q[hh ++ ];//出队列
        int a = t.x, b = t.y, s = t.s;//取出点的坐标及其迭代次数
        if(s == k) break;//如果该点的迭代次数等于最大迭代次数,bfs结束
        for (int i = 0; i < 4; i ++ )//枚举四个向量
        {
            int x = a + dx[i], y = b + dy[i];
            //如果加了偏移量的点并没有越界且还是空地的话,就把空地变为草
            if(x >= 1 && y >= 1 && x <= n && y <= m && g[x][y] == '.')
            {
                g[x][y] = 'g';//空地变为草
                q[ ++ tt] = {x, y, s + 1};//将该点入队列,迭代次数加1
            }
        }
    }
}

int main()
{
    cin.tie(0);
    scanf("%d%d", &n, &m);
    hh = 0, tt = -1;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            char c;
            cin >> c;
            //如果此时的坐标是草,则加入到队列中去,迭代次数为0
            if(c == 'g') q[ ++ tt] = {i, j, 0};
            g[i][j] = c;
        }
    }
    scanf("%d", &k);
    
    bfs();
    
    for (int i = 1; i <= n; i ++ )//输出答案
    {
        for (int j = 1; j <= m; j ++ )
        {
            printf("%c", g[i][j]);
        }
        puts("");
    }
    
    return 0;
}
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
64
65
66
67
68
69
70