Thursday, March 14, 2013

Spiral Matrix

/*
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].
*/
class Solution {
public:
    void printOutRound(vector<vector<int>> matrix, int m, int n, int step, vector<int> & result){
        int i;
       
        if((m-2*step)==0 || (n-2*step)==0) return;
       
        if((m-2*step)==1){
          for(i=step; i<=(n-step-1); i++){
            result.push_back(matrix[step][i]);
          }
          return;
        }
       
        if((n-2*step)==1){
          for(i=step; i<=(m-step-1); i++){
            result.push_back(matrix[i][step]);
          }
          return;
        }
       
        for(i=step; i<=(n-step-2); i++){
          result.push_back(matrix[step][i]);
        }
        for(i=step; i<=(m-step-2); i++){
          result.push_back(matrix[i][n-step-1]);
        }
        for(i=(n-step-1); i>=(step+1); i--){
          result.push_back(matrix[m-step-1][i]);
        }
        for(i=(m-step-1); i>=(step+1); i--){
          result.push_back(matrix[i][step]);
        }
    }
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> result;
        int m = matrix.size();
        if(m==0) return result;
        int n = matrix[0].size();
        if(n==0) return result;
       
        int limit = min(m, n);
        int round = limit/2;
       
        int i;
        for(i=0; i<=round; i++){
          printOutRound(matrix, m, n, i, result);
        }
       
        return result;
    }
};

No comments:

Post a Comment