LeetCode 54/59 Spiral Matrix I/II：螺旋矩陣遍歷與生成

Spiral Matrix I：螺旋順序輸出矩陣元素

題目

給定 m×n 矩陣，按順時針螺旋順序返回所有元素。例：[[1,2,3],[4,5,6],[7,8,9]] → [1,2,3,6,9,8,7,4,5]。

DFS + 訪問標記法

四個方向循環：右 → 下 → 左 → 上。用 visited 數組標記已訪問，遇到邊界或已訪問轉向。遞歸或迭代均可。

代碼

class Solution {
    void dfs(int x, int y, int m, int n, vector<vector<int>>& mat, vector<int>& res, vector<vector<int>>& vis) {
        vis[x][y] = 1; res.push_back(mat[x][y]);
        // 右
        while (y+1 < n && !vis[x][y+1]) { y++; vis[x][y]=1; res.push_back(mat[x][y]); }
        // 下
        while (x+1 < m && !vis[x+1][y]) { x++; vis[x][y]=1; res.push_back(mat[x][y]); }
        // 左
        while (y-1 >= 0 && !vis[x][y-1]) { y--; vis[x][y]=1; res.push_back(mat[x][y]); }
        // 上
        while (x-1 >= 0 && !vis[x-1][y]) { x--; vis[x][y]=1; res.push_back(mat[x][y]); }
        // 遞歸進入內層
        if (y+1 < n && !vis[x][y+1]) dfs(x, y+1, m, n, mat, res, vis);
    }
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        int m = matrix.size(); if (m==0) return res;
        int n = matrix[0].size();
        vector<vector<int>> vis(m, vector<int>(n, 0));
        dfs(0, 0, m, n, matrix, res, vis);
        return res;
    }
};

Spiral Matrix II：生成螺旋矩陣

題目

給定 n，生成 n×n 矩陣，元素 1~n² 按螺旋順序填充。例：n=3 → [[1,2,3],[8,9,4],[7,6,5]]。

同構 DFS 填充

邏輯與 I 題相同，只是將「讀取」改為「寫入」，維護計數器 val 從 1 遞增。

代碼

class Solution {
    void dfs(int x, int y, int n, vector<vector<int>>& mat, int& val) {
        mat[x][y] = val++;
        while (y+1 < n && !mat[x][y+1]) { y++; mat[x][y] = val++; }
        while (x+1 < n && !mat[x+1][y]) { x++; mat[x][y] = val++; }
        while (y-1 >= 0 && !mat[x][y-1]) { y--; mat[x][y] = val++; }
        while (x-1 >= 0 && !mat[x-1][y]) { x--; mat[x][y] = val++; }
        if (y+1 < n && !mat[x][y+1]) dfs(x, y+1, n, mat, val);
    }
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> mat(n, vector<int>(n, 0));
        int val = 1;
        if (n > 0) dfs(0, 0, n, mat, val);
        return mat;
    }
};

複雜度與優化

• 時間：O(m×n) / O(n²)，每個元素訪問一次。
• 空間：O(m×n) 訪問標記 / 輸出矩陣。
• 可優化為 O(1) 額外空間（層層收縮邊界），但 DFS 寫法更直觀易懂。