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版本

//之后需要设计一个非递归的版本

//甚至给定(i,j)推断给定位置的value

class Solution {
public:
    void dfs(vector<vector<int> > &matrix,vector<vector<int> > &visit,vector<int> &ans,int direction,int i, int j){
        ans.push_back(matrix[i][j]);
        visit[i][j] = 1;

        static const int d[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};

        for(int k = 0; k < 4; k++){
            int d1 = (direction + k)%4;
            int dx = i + d[d1][0];
            int dy = j + d[d1][1];
            if (dx >= 0 && dx < matrix.size() && dy >= 0 && dy < matrix[0].size() && !visit[dx][dy]){
                dfs(matrix,visit,ans,d1,dx,dy);
            }
        }
    }
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> ans;
        if (matrix.size() == 0)  return ans;  
        vector<vector<int> > visit(matrix.size());
        for(int i = 0; i < visit.size(); i++){
            visit[i].resize(matrix[i].size(),0);
        }

        int direction = 0;
        dfs(matrix,visit,ans,0,0,0);
        return ans;
    }
};

原文链接: https://www.cnblogs.com/kwill/p/3194581.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍