Spiral Matrix

好久没写文章了...
自罚30大板
在刷leetcode
就继续更新吧

Q：Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.


eg  1:
Input:
[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]

eg 2:
Input:
[
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]  

题目很好理解，就是把一个矩阵螺旋着输出。
看到这个题目，我首先就想着使用深度优先进行搜索。这有点像迷宫的搜索，我们可以定义搜索规则如下：

定义一个辅助矩阵，判断这个cell是否被搜索过。
eg 
[
  [1, 1, 1],          
  [1, 1, 1],
  [1, 1, 1]
]
在这里，1代表未被搜索过，0代表已经被搜索过。
当我们搜索完第一行，matrix变成
[
 [0, 0, 0 ],
 [1, 1, 1 ],
 [1, 1, 1]
]
这时候我们只有一个方向可以继续往下走，就是朝下，因为上下左右都是无法走的（0也是无法走的），类似地，可以一直走到这个状态
[
 [0, 0, 0 ],
 [0, 1, 0 ],
 [0, 0, 0 ]
]
然后就只剩1可以走啦，也就是我们的搜索结束了ORZ

也就是说我们需要定义的变量有以下几个：
1 现在前进的方向direction当只有一个方向可以前行的时候进行改变
2 保存答案的数组 
3 现在的位置，以便于下一次进行Move的时候方便找到初始位置
4 状态数组

然后就开始愉快地撸码。

/**
  direction： 方向
  cur_i，cur_j：现在的位置
  recMatrix： 状态数组
  ans： 保存答案的数组
**/
class Solution {
    void move(int direction,int cur_i, int cur_j, vector<vector<int>>& matrix, vector<vector<int>>& recMatrix, vector<int>& ans){
        if(direction == 0){
            if( cur_j >= matrix[0].size() || recMatrix[cur_i][cur_j] == 0 ) return; //先判断是否还有路可走，没有的话返回
            for( int j = cur_j; ;j++){  //然后开始走，并且记录答案 
                if( j < matrix[cur_i].size() && recMatrix[cur_i][j] != 0 ){
                    cout << matrix[cur_i][j] << endl;
                    ans.push_back(matrix[cur_i][j]);
                    recMatrix[cur_i][j] = 0;
                    cur_j =j;
                }
                else break;
            }
            direction = 1;
            move(direction, cur_i + 1, cur_j , matrix, recMatrix, ans);
        }
        else if(direction == 1){
             if( cur_i >= matrix.size() || recMatrix[cur_i][cur_j] == 0 ) return;
             for( int i = cur_i; ;i++){
                if( i < matrix.size() && recMatrix[i][cur_j] != 0 ){
                    ans.push_back(matrix[i][cur_j]);
                    recMatrix[i][cur_j] = 0;
                    cur_i =i;
                }
                else break;
            }
            direction = 2;
            move(direction, cur_i , cur_j - 1, matrix, recMatrix, ans);
        }
        else if(direction == 2){
             if( cur_j < 0 || recMatrix[cur_i][cur_j] == 0 ) return;
              for( int j= cur_j;; j--){
                if( j >= 0 && recMatrix[cur_i][j] != 0 ){
                    ans.push_back(matrix[cur_i][j]);
                    recMatrix[cur_i][j] = 0;
                    cur_j =j;
                }
                else break;
            }
            direction = 3;
            move(direction, cur_i - 1, cur_j , matrix, recMatrix, ans);
        }
         else if(direction == 3){
              if( cur_i < 0 || recMatrix[cur_i][cur_j] == 0 ) return;
             for( int i = cur_i; ;i--){
                if( i >= 0 && recMatrix[i][cur_j] != 0 ){
                    ans.push_back(matrix[i][cur_j]);
                    recMatrix[i][cur_j] = 0;
                    cur_i =i;
                }
                else break;
            }
            direction = 0;
            move(direction, cur_i , cur_j + 1, matrix, recMatrix, ans);
        }
    }
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> res;
        // 定义的状态举证
        vector<vector<int>> recMatrix;
        if(matrix.size() ==0 ) return res;
        // 初始化
        for( int i = 0; i< matrix.size(); i++){
            vector<int> tempMatrix;
            for( int j = 0; j<matrix[i].size(); j++ ){
                tempMatrix.push_back(1);
            }
            recMatrix.push_back(tempMatrix);
        }
        // direction 0:right 1:down 2:left 3:up
        int direction = 0;
        move(0, 0, 0, matrix, recMatrix, res);
        return res;
    }
};

提交结果 AC beats 100% 看来只有这一个解了。其实这个状态数组完全是不需要的，但是我太懒了，AC了就不想改了，读者也可是实现抛弃这个状态数组进行实现。