ZOJ 3810 A Volcanic Island 構造題另一解法

題目重述

同 ID 208191，此為另一份構造代碼，邏輯更精簡。

核心構造邏輯

void solve(int n) {
    memset(g, 0, sizeof(g));
    for (int i = 0; i < n; ++i) g[0][i] = 3;  // 第一行顏色 3 (Y)
    
    int k = (n - 1) / 2, col = 1;
    // 前半部分：之字形填充
    for (int i = 0; i < k; ++i) {
        for (int j = 1; j <= i + 1; ++j) g[j][i + 1] = col;
        for (int j = i + 1; j < n; ++j) g[j][i] = col;
        col = 3 - col;  // 在 1(G) 和 2(R) 間切換
    }
    // 中間列特殊處理
    for (int i = k; i < n; ++i) {
        for (int j = 2; j <= i + 2; ++j) g[j][i + 2] = col;
        g[i + 2][i + 1] = col;
        for (int j = i + 2; j < n; ++j) g[j][i] = col;
        col = 3 - col;
    }
    // 輸出映射：0=B, 1=G, 2=R, 3=Y
    const char* c = "BGRY";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) printf("%c", c[g[i][j]]);
        puts("");
    }
}

特判情況

• n = 1：輸出 "B"
• n = 6：硬編碼 6×6 方案
• n = 2,3,4：No solution!
• n ≥ 5 且 n ≠ 6：調用 solve(n)

完整主程序

int main() {
    int cas, n; scanf("%d", &cas);
    while (cas--) {
        scanf("%d", &n);
        if (n == 1) puts("B");
        else if (n == 6) {
            const char* s[6] = {"BBBBBB","GGRGRR","GRRGRB","GRGGRB","GRGRRB","GRGBBB"};
            for (int i = 0; i < 6; ++i) puts(s[i]);
        } else if (n >= 5) solve(n);
        else puts("No solution!");
    }
    return 0;
}

與前一解法對比

解法二更優雅，通過觀察發現 n≥5 時統一構造模式，僅 n=6 因對稱性導致形狀衝突需特判。構造題關鍵在於找到通用規律，減少分類討論。