Leetcode --- Spiral Matrix
===
## dfs

方向依序為右,下,左,上，唯一會遇到問題的是當我們在左下角遇到可以往上又可以往右的會先選擇往右，但我們要爬到最上才開始往右，所以多一個參數控制往上爬到底

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        dfs(matrix, 0, 0, 0, res);
        return res;
    }

    void dfs(vector<vector<int>>& matrix, int i, int j, int isUp, vector<int>& res)
    {
        if(i>= matrix.size() || i< 0 || j>= matrix[0].size() || j< 0 || matrix[i][j]== 999) return;
        res.push_back(matrix[i][j]);
        matrix[i][j]= 999;
        if(isUp) dfs(matrix, i- 1, j, 1, res);
        dfs(matrix, i, j+ 1, 0, res);
        dfs(matrix, i+ 1, j, 0, res);
        dfs(matrix, i, j- 1, 0, res);
        dfs(matrix, i- 1, j, 1, res);
    }
};

## Brute Force

dfs在這題向上並不直觀，暴力解為不斷的往右往下往左往上，並在每次去縮減matrix的存取範圍

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& m) {
        int left= 0, right= m[0].size()-1, top= 0, bottom= m.size()-1, mode= 0;
        vector<int> res;
        while(left<= right && top <= bottom)
        {
            switch(mode)
            {
                case 0:
                    //right
                    for(int i= left; i<= right; ++i)
                    {
                        res.push_back(m[top][i]);
                    }
                    ++top;
                    break;
                case 1:
                     //down
                    for(int i= top; i<= bottom; ++i)
                    {
                        res.push_back(m[i][right]);
                    }
                    --right;
                    break;
                case 2:
                    //left
                    for(int i= right; i>= left; --i)
                    {
                        res.push_back(m[bottom][i]);
                    }
                    --bottom;
                    break;
                case 3:
                    //up
                    for(int i= bottom; i>= top; --i)
                    {
                        res.push_back(m[i][left]);
                    }
                    ++left;
                    break;
            }
            mode= (mode+ 1)% 4;
        }
        return res;
    }
};

###### tags: `Leetcode` `Medium` `DFS`