問題描述

在 n×n 方陣中按蛇形填入 1 到 n²。n=4 時：

10 11 12  1
 9 16 13  2
 8 15 14  3
 7  6  5  4

規律：右→左→下→左→上→右→... 循環。

算法思路

1. 從右上角 (1, n) 開始，初始方向向左
2. 四個方向循環：下 → 左 → 上 → 右
3. 每步檢查：不越界 且 目標位置未填充 (值為 0)
4. 滿足則移動並填入下一數字，否則換方向

完整代碼

#include 
#include 

int a[10][10];

int main() {
    int n, count, i, j;
    memset(a, 0, sizeof(a));
    scanf("%d", &n);

    // 起始位置：第1行第n列
    i = 1; j = n;
    count = a[i][j] = 1;

    while (count < n*n) {
        // 向下
        while (i < n && a[i+1][j] == 0) a[++i][j] = ++count;
        // 向左
        while (j > 1 && a[i][j-1] == 0) a[i][--j] = ++count;
        // 向上
        while (i > 1 && a[i-1][j] == 0) a[--i][j] = ++count;
        // 向右
        while (j < n && a[i][j+1] == 0) a[i][++j] = ++count;
    }

    // 輸出
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++)
            printf("%3d%c", a[i][j], j==n?'\n':' ');
    }
    return 0;
}

運行示例

輸入: 4
輸出:
 10  11  12   1
  9  16  13   2
  8  15  14   3
  7   6   5   4

複雜度分析

• 時間：O(n²) — 每個位置恰好訪問一次
• 空間：O(n²) — 存儲矩陣
• 邊界：n ≤ 8（題目限制），數組開 [10][10] 足夠

擴展思考

• 如何修改起始位置與初始方向生成不同蛇形？
• 能否用方向向量數組 dx[4]={1,0,-1,0}, dy[4]={0,-1,0,1} 簡化代碼？
• 三維蛇形填充如何實現？