Thursday, March 14, 2013

Spiral Matrix II

/*
Spiral Matrix II
Given an integer n, generate a square matrix filled with elements from 1 to n2 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:
    void fillOneRound(vector<vector<int>> & result, int const n, int & curr, int const step){
       if ((n-2*step)==0) return;
      
       if (n-2*step==1 && curr <= n*n) {
          result[step][step] = curr;
          curr++;
       }
      
       int i;
       for(i=step; i<=(n-step-2) && curr<=n*n; i++){
         result[step][i] = curr;
         curr++;
       }
       for(i=step; i<=(n-step-2) && curr<=n*n; i++){
         result[i][n-step-1] = curr;
         curr++;
       }
       for(i=(n-step-1); i>=(step+1) && curr<=n*n; i--){
         result[n-step-1][i] = curr;
         curr++;
       }
       for(i=(n-step-1); i>=(step+1) && curr<=n*n; i--){
         result[i][step] = curr;
         curr++;
       }
    }
   
    vector<vector<int> > generateMatrix(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int>> result;
       
        if(n<=0) return result;
       
        vector<int> line(n, 0);
        result.insert(result.begin(), n, line);
       
        int round = n/2;
       
        int step;
       
        int currNum = 1;
       
        for(step=0; step<=round; step++){
           fillOneRound(result, n, currNum, step);
        }
       
        return result;
    }
};

No comments:

Post a Comment