2020蓝桥杯模拟——长草

 1.题目描述

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

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

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

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

2.输入格式

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

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

3.输出格式

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

4.样例输入

4 5
.g...
.....
..g..
.....
2

5.样例输出

gggg.
gggg.
ggggg
.ggg.

6、数据范围

2≤n,m≤1000，1≤k≤1000。

7.原题链接

长草

8.解题思路

很经典的bfs思路，与传统的走迷宫bfs相比，这道题不需要用队列中已经搜到的点去拓展更外层的点，所以搜完四个方向时，不需要将这四个方向的点加入队列。下面是代码。

#include <bits/stdc++.h>
 
#define x first
#define y second
 
using namespace std;
 
typedef pair<int, int> PII;
 
const int N = 1010;
 
int n, m;
char g[N][N];
bool st[N][N];
queue<PII> q;
 
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
 
void bfs(int x, int y)
{
    q.push({x, y});
    st[x][y] = true;
    
    while (q.size())
    {
        auto t = q.front();
        q.pop();
 
        for (int i = 0; i < 4; i ++ ) 
        {
            int a = t.x + dx[i], b = t.y + dy[i];
            if (a < 0 || a >= n || b < 0 || b >= m) continue;
            if (g[a][b] == 'g') continue;
 
            g[a][b] = 'g';
            st[a][b] = true;
            //q.push({a, b});这句话不要写
        }
    }
}
 
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i ++ ) scanf("%s", g[i]);
 
    int k;
    cin >> k;
    while (k -- )
    {
        memset(st, 0, sizeof st);
        for (int i = 0; i < n; i ++ ) 
            for (int j = 0; j < m; j ++ ) 
                if (g[i][j] == 'g' && !st[i][j]) 
                    bfs(i, j);
    }    
 
    for (int i = 0; i < n; i ++ ) cout << g[i] << endl;
    return 0;
}