提出 #76710677

---

ソースコード 拡げる

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
    // Optimize standard I/O operations for competitive programming
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int H, W, Q;
    if (!(cin >> H >> W >> Q)) return 0;

    vector<string> grid(H);
    for (int i = 0; i < H; ++i) {
        cin >> grid[i];
    }

    // Direction arrays for 4-connectivity
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};

    // is_facing[i][j] will be true if the building at (i, j) already faces a road
    vector<vector<bool>> is_facing(H, vector<bool>(W, false));
    int facing_roads_count = 0;

    // Initial check: scan all buildings to see if they already face a road
    for (int i = 0; i < H; ++i) {
        for (int j = 0; j < W; ++j) {
            if (grid[i][j] == 'B') {
                bool faces = false;
                for (int d = 0; d < 4; ++d) {
                    int ni = i + dr[d];
                    int nj = j + dc[d];
                    if (ni >= 0 && ni < H && nj >= 0 && nj < W) {
                        if (grid[ni][nj] == 'R') {
                            faces = true;
                            break;
                        }
                    }
                }
                if (faces) {
                    is_facing[i][j] = true;
                    facing_roads_count++;
                }
            }
        }
    }

    // Lambda helper to convert an 'E' cell on the perimeter to 'R' and update neighbors
    auto activate_cell = [&](int r, int c) {
        if (grid[r][c] == 'E') {
            grid[r][c] = 'R';
            // Check all 4 neighbors of this newly created road
            for (int d = 0; d < 4; ++d) {
                int nr = r + dr[d];
                int nc = c + dc[d];
                if (nr >= 0 && nr < H && nc >= 0 && nc < W) {
                    if (grid[nr][nc] == 'B' && !is_facing[nr][nc]) {
                        is_facing[nr][nc] = true;
                        facing_roads_count++;
                    }
                }
            }
        }
    };

    // Process each construction query
    for (int k = 0; k < Q; ++k) {
        int U, D, L, R;
        cin >> U >> D >> L >> R;
        // Convert to 0-indexed coordinates
        U--; D--; L--; R--;

        // We only need to process the perimeter of the rectangle.
        // Top and Bottom rows
        for (int c = L; c <= R; ++c) {
            activate_cell(U, c);
            activate_cell(D, c);
        }
        // Left and Right columns
        for (int r = U; r <= D; ++r) {
            activate_cell(r, L);
            activate_cell(r, R);
        }

        // Output the total count after this operation
        cout << facing_roads_count << "\n";
    }

    return 0;
}

提出情報

ジャッジ結果