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
- 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; } }
- 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; }