劍指Offer：順時針打印矩陣（九度OJ 1391）

題目描述

輸入一個矩陣，按照從外向內以順時針順序依次打印出每一個數字。

輸入格式

• 多測試用例，EOF 結束
• 每用例第一行：m n（行數、列數）
• 接下來 m 行，每行 n 個整數

輸出格式

順時針螺旋順序輸出所有元素，空格分隔，換行結束。

解題思路：層層剝洋蔥

核心邏輯

定義四個邊界：top、bottom、left、right。每圈打印四條邊：

1. 左→右：top 行，left~right
2. 上→下：right 列，top+1~bottom
3. 右→左：bottom 行，right-1~left（需 top < bottom）
4. 下→上：left 列，bottom-1~top+1（需 left < right）

每圈結束收縮邊界：top++, bottom--, left++, right--，直到 top > bottom 或 left > right。

邊界條件處理

• 單行矩陣：只執行步驟 1
• 單列矩陣：執行步驟 1、2
• 單元素：只執行步驟 1

完整代碼

#include <stdio.h>
#include <stdlib.h>

#define MAX_M 1000
#define MAX_N 1000

int matrix[MAX_M][MAX_N];

int main() {
    int m, n;
    while (scanf("%d %d", &m, &n) != EOF) {
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                scanf("%d", &matrix[i][j]);
        
        int top = 0, bottom = m - 1;
        int left = 0, right = n - 1;
        int first = 1;  // 控制輸出格式
        
        while (top <= bottom && left <= right) {
            // 左→右
            for (int j = left; j <= right; j++) {
                if (!first) printf(" ");
                printf("%d", matrix[top][j]);
                first = 0;
            }
            top++;
            if (top > bottom) break;
            
            // 上→下
            for (int i = top; i <= bottom; i++) {
                printf(" %d", matrix[i][right]);
            }
            right--;
            if (left > right) break;
            
            // 右→左
            if (top <= bottom) {
                for (int j = right; j >= left; j--) {
                    printf(" %d", matrix[bottom][j]);
                }
                bottom--;
            }
            if (top > bottom) break;
            
            // 下→上
            if (left <= right) {
                for (int i = bottom; i >= top; i--) {
                    printf(" %d", matrix[i][left]);
                }
                left++;
            }
        }
        printf("\n");
    }
    return 0;
}

複雜度分析

• 時間複雜度：O(m×n)，每個元素訪問一次
• 空間複雜度：O(1) 額外空間（不計輸入矩陣）

測試用例