BFS

k个月后多少空地长草

#include<bits/stdc++.h>

using namespace std;
const int N = 1005;
struct PII{
    int first;
    int second;
};
int len;
char Map[N][N];
int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
int n, m, k;
queue<PII> q;
void bfs(){
    while(!q.empty() && k > 0){
        PII t = q.front();
        q.pop();
        int x = t.first;int y = t.second;
        for(int i = 0; i < 4; i ++){
            int xx = x + dx[i];
            int yy = y + dy[i];
            if(xx >= 1 && yy >= 1 && xx <= n && yy <= m && Map[xx][yy] != 'g')
            {
                q.push({xx, yy});
                Map[xx][yy] = 'g';
            }
        }
        len --;
        if(len == 0){
            k --;
            len = q.size();
        }
    }
}
int main()
{
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        for(int j = 1; j <= m; j ++){
            cin >> Map[i][j];
            if(Map[i][j] == 'g'){
                q.push({i, j});
            }
        }
    }
    len = q.size();
    cin >> k;
    bfs();
    for (int i = 1; i <= n; i ++ ){
        for (int j = 1; j <= m; j ++ ){
            cout << Map[i][j];
        }
        cout << '\n';
    }
    return 0;
}