# 54 - Spiral Matrix

解法一 - 以一圈為單位思考

如果沒有想過這種題目，一開始要寫出 general 的解會發現腦袋有點打結，因為跟我們習以為常的資料 iterate 方式不太一樣，所以我們可以先從 3x3 開始，寫出一個很醜的一圈輸出解：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // Assume 3x3 only 
        vector<int> res;

        int m = matrix.size();

        int n;
        if(m > 0)
            n = matrix[0].size();

        // Right
        int j;
        for(j=0; j<n; j++) {
            res.push_back(matrix[0][j]);
        }

        j = n-1;

        // Down
        int i;
        for(i=1; i<m; i++) {
            res.push_back(matrix[i][j]);
        }

        i = m-1;

        // Left
        for(j=n-2; j>=0; j--) {
            res.push_back(matrix[i][j]);
        }

        j = 0;

        // Up
        for(i=m-2;i>=1; i--)
            res.push_back(matrix[i][j]);

        for(auto k: res)
            cout << k << " ";
        cout << endl;

        return res;
    }
};

/*
// idea: 
m row, n col
1st row
n-th col
mth row
1-th col

2nd row
n-1 th col
m-1 th row
2nd col
*/

這個解法很醜，而且一點也不 general，可是他可以提供我們一個切入點，從這個程式碼當中，隱約可以看出核心要注意的點就是每次輸出一個 row/col 時，i & j 的值和上下界。感覺好像可以用 up, down, left, right 來紀錄目前輸出的上下界，跟每次要輸出時，i or j 的值。

加入 up, down, left, right 後，我們得到一個這樣的解：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        // Assume 3x3 only 
        vector<int> res;

        int m = matrix.size();

        int n;
        if(m > 0)
            n = matrix[0].size();

        int up=0, down=m-1, left=0, right=n-1;


        // Right
        int i = up, j = left;
        for(; j<right+1; j++) 
            res.push_back(matrix[i][j]);

        up++;
        j = right;

        // Down
        for(i=up; i<down+1; i++) 
            res.push_back(matrix[i][j]);

        right--;
        i = down;

        // Left
        for(j=right; j>=left; j--) {
            res.push_back(matrix[i][j]);
        }

        down--;
        j = left;

        // Up
        for(i=down;i>=up; i--)
            res.push_back(matrix[i][j]);

        left++;
        i = up;

        for(auto k: res)
            cout << k << " ";
        cout << endl;

        return res;
    }
};

/*
// idea: 
m row, n col
1st row
n-th col
mth row
1-th col

2nd row
n-1 th col
m-1 th row
2nd col
*/

這個實作雖然看起來很醜，不過很好地呈現了一次從 naive 到可以 work 的實作過程。而且跑起來時間效率也不錯：

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Spiral Matrix. Memory Usage: 8.6 MB, less than 39.69% of C++ online submissions for Spiral Matrix.

第三版程式碼：

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        if(matrix.empty()) return res;

        int m = matrix.size();
        int n = matrix[0].size();
        int up=0, down=m-1, left=0, right=n-1;

        while(up<=down && left <= right) {
            // Right
            for(int col = left; col<=right; col++)  res.push_back(matrix[up][col]);
            up++;
            if(up > down) break;

            // Down
            for(int row=up; row<=down; row++)  res.push_back(matrix[row][right]);
            right--;
            if(right < left) break;

            // Left
            for(int col=right; col>=left; col--) res.push_back(matrix[down][col]);
            down--;

            // Up
            for(int row=down;row>=up; row--) res.push_back(matrix[row][left]);
            left++;
        }

        return res;
    }
};

解法二 - 模擬自己在 matrix 裡面走，紀錄方向

先記錄一下還可以這樣解：