LeetCode OJ：Spiral Matrix（螺旋矩阵）

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

For example,
Given the following matrix:

[

 [ 1, 2, 3 ],

 [ 4, 5, 6 ],

 [ 7, 8, 9 ]

]

You should return [1,2,3,6,9,8,7,4,5].

典型的dfs问题，与前面一个问题比较像，代码如下。单独维护一个数组记录是否已经走过某个格子，注意边界条件的判断就可以了，代码如下：

 class Solution {

 public:

     vector<int> spiralOrder(vector<vector<int>>& matrix) {

         drt = vector<vector<int>>{{,},{,},{-,},{,-}};   //四个方向

         mark = vector<vector<bool>>(,vector<bool>(,false));

         ret.clear();

         if(!matrix.size() || !matrix[].size())

             return ret;

         dfs(matrix, , , -);//这里取-1是为了能从(0,0)开始。

         return ret;

     }

     void dfs(vector<vector<int>> & matrix, int direct, int x, int y)

     {

         for(int i = ; i < ; ++i){

             int j = (direct + i) % ;

             int tx = x + drt[j][];

             int ty = y + drt[j][];

             if(tx >=  && tx < matrix.size() &&

                 ty >=  && ty < matrix[].size() &&

                 mark[tx][ty] == false){

                 mark[tx][ty] = true;

                 ret.push_back(matrix[tx][ty]);

                 dfs(matrix, j, tx, ty);

             }

         }

     }

 private:

     vector<vector<int>> drt;

     vector<vector<bool>> mark;

     vector<int> ret;

 };

巴特西

LeetCode OJ：Spiral Matrix（螺旋矩阵）

最新文章

热门文章