The 11th Blue Bridge Cup provincial Simulation Competition - Changcao

Title Description

Xiao Ming has an open space, which he divides into n n n line m m The length of each row and colu m n is 1 1 1.

Xiao Ming chose some small open spaces and planted grass, while others remained open spaces.

These grasses grow very fast. Every month, the grass will grow out. If a small piece of grass is planted, it will expand to its upper, lower, left and right open spaces,

These four plots of open space will be turned into grass plots. Please tell Xiao Ming, k k Where will there be grass in the open space after k months.

Input format

The first line of input contains two integers n , m n, m n,m.

next n n n rows, each containing m m m letters, indicating the initial open space state, and there is no space between the letters. If it is a decimal point, it means empty space; if the letter is g g g. It means planting grass.

Next, include an integer k k k. Among them, 2 ≤ n , m ≤ 1000 ， 1 ≤ k ≤ 10002 ≤ n , m ≤ 1000 ， 1 ≤ k ≤ 1000 2 \leq n, m \leq 1000，1 \leq k \leq 10002≤n,m≤1000，1≤k≤1000 2≤n,m≤1000，1≤k≤10002≤n,m≤1000，1≤k≤1000.

Output format

output n n n rows, each containing m m m letters, indicating the state of the open space after kk months. If it is a decimal point, it means empty space; if the letter is g g g. It means grass.

Input sample:

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

Output example:

gggg.
gggg.
ggggg
.ggg.

Operational limits

Maximum running time: 1s
Maximum operating memory: 256M

General idea of the topic

When in the first k k At k iterations, the map is output.
Grass can only spread around (up, down, left and right).
The following figure shows an example of the simulation:

Problem solving ideas

1. Store the map in g[N][N]. If the point is grass, put it in the queue, and the number of iterations is 0.

for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            char c;
            cin >> c;
            //If the coordinate at this time is grass, it will be added to the queue, and the number of iterations is 0
            if(c == 'g') q[ ++ tt] = {i, j, 0};
            g[i][j] = c;
        }
    }

1. bfs is used to search all points on the map that are not grass, and all open spaces are turned into grass under the specified maximum number of iterations.

void bfs()
{
    while (hh <= tt)//When there are no elements in the queue, the loop is pushed out
    {
        auto t = q[hh ++ ];//Out of queue
        int a = t.x, b = t.y, s = t.s;//Take out the coordinates of the point and the number of iterations
        if(s == k) break;//If the number of iterations at this point is equal to the maximum number of iterations, bfs ends
        for (int i = 0; i < 4; i ++ )//Enumerate four vectors
        {
            int x = a + dx[i], y = b + dy[i];
            //If the offset point does not cross the boundary and is still open space, turn the open space into grass
            if(x >= 1 && y >= 1 && x <= n && y <= m && g[x][y] == '.')
            {
                g[x][y] = 'g';//The open space turns into grass
                q[ ++ tt] = {x, y, s + 1};//Put the point in the queue and add 1 to the number of iterations
            }
        }
    }
}

The code is as follows~

c + + code

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

using namespace std;

const int N = 1010;

struct Edge
{
    int x, y, s;
} q[N * N];//x. Y: coordinates of points, s: number of iterations

char g[N][N];//Map
int hh, tt;//hh: team leader, tt: team tail
int n, m;
int k;//Maximum number of iterations
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//Four vectors represent up, down, left and right

void bfs()
{
    while (hh <= tt)//When there are no elements in the queue, the loop is pushed out
    {
        auto t = q[hh ++ ];//Out of queue
        int a = t.x, b = t.y, s = t.s;//Take out the coordinates of the point and the number of iterations
        if(s == k) break;//If the number of iterations at this point is equal to the maximum number of iterations, bfs ends
        for (int i = 0; i < 4; i ++ )//Enumerate four vectors
        {
            int x = a + dx[i], y = b + dy[i];
            //If the offset point does not cross the boundary and is still open space, turn the open space into grass
            if(x >= 1 && y >= 1 && x <= n && y <= m && g[x][y] == '.')
            {
                g[x][y] = 'g';//The open space turns into grass
                q[ ++ tt] = {x, y, s + 1};//Put the point in the queue and add 1 to the number of iterations
            }
        }
    }
}

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;
            //If the coordinate at this time is grass, it will be added to the queue, and the number of iterations is 0
            if(c == 'g') q[ ++ tt] = {i, j, 0};
            g[i][j] = c;
        }
    }
    scanf("%d", &k);
    
    bfs();
    
    for (int i = 1; i <= n; i ++ )//Output answer
    {
        for (int j = 1; j <= m; j ++ )
        {
            printf("%c", g[i][j]);
        }
        puts("");
    }
    
    return 0;
}