Codeforces 525D Arthur and Walls：貪心 BFS 將房間擴展為矩形

問題描述

給定 n,m ≤ 2000 網格，'*' 為牆，'.' 為空地。房間 = 連通空地區域（4 連通）。目標：拆除最少牆（*→.），使所有房間變為矩形。輸出最終網格。多解任意。

核心觀察：貪心條件

一個牆格 (i,j) 必須被拆除，當且僅當它是某個 2×2 子網格中唯一的牆（其餘三格為空地）。因為若保留它，這三格空地屬於同一房間，但房間形狀非矩形（有凹陷）。拆除它後，四格合併為矩形房間。

算法：BFS 遍歷待拆牆

1. 初始掃描全網格，找出所有「唯一牆」的 2×2 窗口，將該牆標記為空地，加入隊列。
2. BFS：彈出牆格 (x,y)，檢查其周圍 3×3 範圍內的所有 2×2 窗口（共 4 個），若某窗口變為「唯一牆」，拆除該牆，入隊。
3. 直到隊列空。剩餘牆即為保留牆。

代碼實現

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
int n, m;
char grid[MAXN][MAXN];
int a[MAXN][MAXN];  // 1=空地, 0=牆
int dx[4]={-1,1,0,0}, dy[4]={0,0,-1,1};

int sum2x2(int x, int y) {  // 左上角為 (x,y) 的 2x2 窗口空地數
    return a[x][y] + a[x][y+1] + a[x+1][y] + a[x+1][y+1];
}

bool should_remove(int x, int y) {
    if (a[x][y]) return false;  // 已是空地
    // 檢查 4 個包含 (x,y) 的 2x2 窗口
    return sum2x2(x,y)==3 || sum2x2(x-1,y)==3 || sum2x2(x,y-1)==3 || sum2x2(x-1,y-1)==3;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        string s; cin >> s;
        for (int j = 1; j <= m; ++j) {
            grid[i][j] = s[j-1];
            a[i][j] = (s[j-1] == '.');
        }
    }
    queue> q;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            if (should_remove(i, j)) {
                a[i][j] = 1;
                q.emplace(i, j);
            }
    while (!q.empty()) {
        auto [x, y] = q.front(); q.pop();
        for (int nx = x-1; nx <= x+1; ++nx)
            for (int ny = y-1; ny <= y+1; ++ny)
                if (nx>=1 && nx<=n && ny>=1 && ny<=m && should_remove(nx, ny)) {
                    a[nx][ny] = 1;
                    q.emplace(nx, ny);
                }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j)
            cout << (a[i][j] ? '.' : '*');
        cout << '\n';
    }
    return 0;
}

複雜度

每個格子最多入隊一次，每次檢查 4 個窗口 O(1)。總時間 O(n·m) ≤ 4×10^6，空間 O(n·m)。

關鍵點

1. 「2×2 唯一牆」是局部必要條件，反複應用直到穩定，保證全局最優（證明基於矩形房間的凸性）。
2. 邊界處理：sum2x2 訪問 x-1,y-1 時需判邊界，代碼中隱式利用 a[0][*]=a[*][0]=0（全局靜態數組初始化為 0）。
3. 輸出任意合法解，BFS 順序不影響最終結果。