C語言演算法：蛇形填數矩陣生成

螺旋矩陣 / 蛇形填數：右→下→左→上 循環邊界縮減法

生成 N×N 矩陣，數字 1 到 N² 按順時針螺旋填入。核心策略：維護四個邊界，每完成一邊就收縮邊界。

完整實作

#include <stdio.h>
#include <string.h>

#define MAX_N 100

int main() {
    int n;
    printf("請輸入矩陣大小 N (1-%d): ", MAX_N);
    if (scanf("%d", &n) != 1 || n < 1 || n > MAX_N) {
        printf("輸入無效\n");
        return 1;
    }
    
    int a[MAX_N][MAX_N];
    memset(a, 0, sizeof(a));
    
    int top = 0, bottom = n - 1;
    int left = 0, right = n - 1;
    int num = 1;
    int target = n * n;
    
    while (num <= target) {
        // 向右：頂行
        for (int j = left; j <= right && num <= target; j++) {
            a[top][j] = num++;
        }
        top++;
        
        // 向下：右欄
        for (int i = top; i <= bottom && num <= target; i++) {
            a[i][right] = num++;
        }
        right--;
        
        // 向左：底行
        for (int j = right; j >= left && num <= target; j--) {
            a[bottom][j] = num++;
        }
        bottom--;
        
        // 向上：左欄
        for (int i = bottom; i >= top && num <= target; i--) {
            a[i][left] = num++;
        }
        left++;
    }
    
    // 輸出矩陣
    printf("\n蛇形填數結果 (N=%d):\n", n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            printf("%4d", a[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}

執行範例 (N=5)

   1   2   3   4   5
  16  17  18  19   6
  15  24  25  20   7
  14  23  22  21   8
  13  12  11  10   9

演算法分析

變體：逆時針螺旋

// 只需調整四個方向順序：下→右→上→左
// 向下：左欄
for (int i = top; i <= bottom; i++) a[i][left] = num++;
left++;
// 向右：底行
for (int j = left; j <= right; j++) a[bottom][j] = num++;
bottom--;
// 向上：右欄
for (int i = bottom; i >= top; i--) a[i][right] = num++;
right--;
// 向左：頂行
for (int j = right; j >= left; j--) a[top][j] = num++;
top++;

變體：不儲存矩陣，直接計算座標值

// 給定 (r, c) 直接計算其值，O(1) 空間
// 需判斷該點在哪一層、哪一邊，較複雜但節省記憶體
// 適合極大 N (如 10^9) 只查詢少數位置的場景

常見錯誤

• 邊界更新順序錯誤 (先填再縮 vs 先縮再填)
• 單行/單列中間矩陣重複填入 (需 num <= target 條件)
• 迴圈條件寫死 j <= right 未考慮邊界已收縮
• 輸出格式未對齊 (用 %4d 或根據最大值動態計算寬度)

應用場景

• 遊戲地圖生成 (迷宮、探索順序)
• 影像處理掃描順序 (Z-order, Hilbert curve 相關)
• 測試資料生成、算法競程題目
• UI 動畫軌跡計算