NYOJ 33 蛇形填數：矩陣層層遞進的構造算法

問題描述

給定 n，生成 n×n 蛇形矩陣。數字從 1 開始，從中心向外呈順時針/逆時針螺旋填充。示例（n=3）：

7 8 1
6 9 2
5 4 3

核心思路：分層構造

矩陣可分解為同心層。每層包含四條邊，按順序填充：

1. 上邊：左 → 右
2. 右邊：上 → 下
3. 下邊：右 → 左
4. 左邊：下 → 上

用變量 i 統一控制四條邊的填充步數，大幅簡化邏輯。

關鍵代碼片段

void fillLayer(int c1, int c2) { // c1=層起始行/列, c2=層終止行/列
    if (c1 == c2) { a[c1][c2] = element++; return; } // 中心單元格
    int i = -1;
    while (++i < c2 - c1) a[c1][c1 + i] = element++; // 上
    i = -1;
    while (++i < c2 - c1) a[c1 + i][c2] = element++; // 右
    i = -1;
    while (++i < c2 - c1) a[c2][c2 - i] = element++; // 下
    i = -1;
    while (++i < c2 - c1) a[c2 - i][c1] = element++; // 左
}

int main() {
    int n; cin >> n;
    int center = 0;
    while (center <= n - 1 - center) {
        fillLayer(center, n - 1 - center);
        center++;
    }
    // 輸出矩陣...
}

附錄：另一種蛇形（順時針外向內）

代碼結構相似，僅填充順序與方向不同。核心仍是「層」與「四邊統一步數」的思想。

心得總結

• 分層思想：將二維問題拆解為一維序列的層層處理。
• 統一變量控制：用單一循環變量 i 遍歷四條邊，避免重複邊界計算。
• 邊界條件：中心點單獨處理（n 為奇數時）。

此類矩陣構造題，關鍵在於找到規律性的填充順序，並用極簡代碼表達幾何邏輯。