Codeforces Round #222 (Div. 1) A. Maze

問題

codeforces.com

解法

まず空いてるマスのすべてを 'X' にし, 'X' となっている好きな点から幅優先探索して '.' を広げていけば良いです。

string field[505];
bool done[505][505];

int n, m, k;

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m >> k;
    int sy, sx, cnt = 0;
    for (int i = 0; i < n; i++) {
        cin >> field[i];
        for (int j = 0; j < m; j++) {
            if (field[i][j] == '.') {
                cnt++;
                field[i][j] = 'X';
                sy = i;
                sx = j;
            }
        }
    }
    queue<pii> que;
    que.push(pii(sy, sx));
    done[sy][sx] = true;
    k = cnt-k;
    while (k > 0) {
        auto p = que.front(); que.pop();
        int y = p.first, x = p.second;
        field[y][x] = '.';
        k--;
        for (int i = 0; i < 4; i++) {
            int ny = y+dy[i], nx = x+dx[i];
            if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
            if (field[ny][nx] == 'X' && !done[ny][nx]) {
                que.push(pii(ny, nx));
                done[ny][nx] = true;
            }
        }
    }
    for (int i = 0; i < n; i++) cout << field[i] << endl;
    return 0;
}