CF 389B Fox and Cross：貪心構造十字架

題目大意

給定 n×n 網格（3≤n≤100），'#' 表示格子。判斷能否用若干個「十字架」（中心加上下左右四格）完全覆蓋所有 '#'，且十字架不重疊。

貪心策略

掃描網格，若遇到 '#'，它必須是某個十字架的「上臂」（因為最上行的 '#' 無法被其他十字架的下臂覆蓋）。檢查其下方、左下、右下、下兩格是否均為 '#'。若是，將這 5 格標記為已用（改為 '.'）；否則無解。最後檢查是否還有剩餘 '#'。

正確性證明

最上行的 '#' 只能作為十字架的上臂（或中心，但中心需要上臂）。若作為中心，則其上方必須有 '#'，矛盾。故最上行 '#' 必為上臂，十字架位置唯一確定。依此向下推，貪心選擇無後效性。

代碼實現（C++）

#include <cstdio>
#include <cstring>
using namespace std;
const int MAXN = 105;
char g[MAXN][MAXN];

int main() {
    int n;
    while (~scanf("%d", &n)) {
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            scanf("%s", g[i]);
            for (int j = 0; j < n; ++j) if (g[i][j] == '#') ++cnt;
        }
        bool ok = (cnt % 5 == 0);
        for (int i = 0; i < n && ok; ++i) {
            for (int j = 0; j < n && ok; ++j) if (g[i][j] == '#') {
                if (j == 0 || j == n-1 || i > n-3 ||
                    g[i+1][j] != '#' || g[i+1][j-1] != '#' ||
                    g[i+1][j+1] != '#' || g[i+2][j] != '#') {
                    ok = false; break;
                }
                g[i+1][j] = g[i+1][j-1] = g[i+1][j+1] = g[i+2][j] = '.';
            }
        }
        puts(ok ? "YES" : "NO");
    }
    return 0;
}