[LeetCode] Spiral Matrix 1 & 2

Spiral Matrix II

Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        if (n == 0) return vector<vector<int> >();
        static const int dy[] = {0,1,0,-1}; // right, down, left, up
        static const int dx[] = {1,0,-1,0};
        vector<vector<int> > res;
        res.resize(n);
        for (int i = 0; i < n; ++i) res[i].resize(n,0);
        int cur = 1;
        for (int i = 0; i < n; ++i) res[0][i] = cur++;
        for (int i = 1; i < n; ++i) res[i][n-1] = cur++;
        for (int i = n-2; i >= 0; --i) res[n-1][i] = cur++;
        
        int y = n-1, x = 0, dir = 3;
        int t = n*n;
        while (cur <= t) {
            if (res[y+dy[dir%4]][x+dx[dir%4]] != 0) {
                dir++; continue;
            }
            y += dy[dir%4];
            x += dx[dir%4];
            res[y][x] = cur++;
        }
        return res;
    }
};

 

@2013-10-03

class Solution {
public:
    vector<vector<int> > generateMatrix(int n) {
        vector<vector<int> > res(n);
        for (int i = 0; i < n; i++) res[i].resize(n);
        gen(1, 0, n - 1, 0, n - 1, res);
        return res;
    }
    
    void gen(int start, int left, int right, int top, int bot, vector<vector<int> >& a) {
        if (left > right || top > bot) return;
        if (left == right) {
            a[left][top] = start ++;
            return;
        }
        else {
            for (int i = left; i <= right; i++) a[top][i] = start++;
            for (int i = top + 1; i < bot; i++) a[i][right] = start++;
            for (int i = right; i >= left; i--) a[bot][i] = start++;
            for (int i = bot - 1; i > top; i--) a[i][left] = start++;
            gen(start, left + 1, right - 1, top + 1, bot - 1, a);
        }
    }
};

 

 

 

Spiral Matrix

 

AC Rate: 436/2242

My Submissions

 

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].

 

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> res;
        int n = matrix.size();
        if (n == 0) return res;
        int m = matrix[0].size();
        gen(res, 0, 0, n-1, m-1, matrix);
        return res;
    }
    
    void gen(vector<int>& res, int left, int top, int bottom, int right, vector<vector<int> >& a) {
        if (left > right || top > bottom) return;
        
        if (left == right) {
            for (int i = top; i <= bottom; i++) res.push_back(a[i][left]);
            return;
        }
        else if (top == bottom) {
            for (int i = left; i <= right; i++) res.push_back(a[top][i]);
            return;
        }
        else {
            for (int i = left; i <= right; i++ ) res.push_back(a[top][i]);
            for (int i = top + 1; i < bottom; i++) res.push_back(a[i][right]);
            for (int i = right; i >= left; i--) res.push_back(a[bottom][i]);
            for (int i = bottom - 1; i > top; i--) res.push_back(a[i][left]);
            gen(res, left + 1, top + 1, bottom - 1, right - 1, a);
        }
    }
};