## Saturday, January 5, 2013

### [LeetCode] 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]`.
» Solve this problem

[解题思路]

[Code]
``````1:    vector<int> spiralOrder(vector<vector<int> > &matrix) {
2:      // Start typing your C/C++ solution below
3:      // DO NOT write int main() function
4:      vector<int> output;
5:      int row_len = matrix.size();
6:      if(row_len ==0) return output;
7:      int col_len = matrix[0].size();
8:      print_order(matrix, 0, row_len, 0, col_len, output);
9:      return output;
10:    }
11:    void print_order(
12:      vector<vector<int> > &matrix,
13:      int row_s,
14:      int row_len,
15:      int col_s,
16:      int col_len,
17:      vector<int>& output)
18:    {
19:      if(row_len<=0 || col_len <=0) return;
20:      if(row_len ==1)
21:      {
22:        for(int i =col_s; i< col_s+col_len; i++)
23:          output.push_back(matrix[row_s][i]);
24:        return;
25:      }
26:      if(col_len ==1)
27:      {
28:        for(int i =row_s; i<row_s + row_len; i++)
29:          output.push_back(matrix[i][col_s]);
30:        return;
31:      }
32:      for(int i =col_s; i<col_s+col_len-1; i++)  //up
33:        output.push_back(matrix[row_s][i]);
34:      for(int i =row_s; i<row_s+row_len-1; i++)   //right
35:        output.push_back(matrix[i][col_s+col_len-1]);
36:      for(int i =col_s; i<col_s+col_len-1; i++)  //bottom
37:        output.push_back(matrix[row_s+row_len-1][2*col_s+ col_len-1 -i]);
38:      for(int i =row_s; i<row_s+row_len-1; i++)  //left
39:        output.push_back(matrix[2*row_s+row_len-1-i][col_s]);
40:      print_order(matrix, row_s+1, row_len-2, col_s+1, col_len-2, output);
41:    }
``````

Update 2014/01/05

``` 1 vector<int> spiralOrder(vector<vector<int> > &matrix) {
2     vector<int> result;
3     int row = matrix.size();
4     if(row == 0) return result;
5     int col = matrix[0].size();
6     if(col == 0) return result;
7
8     //define the step for 4 directions
9     int x[4] = { 1, 0, -1, 0 };
10     int y[4] = { 0, 1, 0, -1 };
11
12     int visitedRows = 0;
13     int visitedCols = 0;
14
15     // define direction: 0 means up, 1 means down, 2 means left, 3 means up
16     int direction = 0;
17     int startx = 0, starty = 0;
18     int candidateNum = 0, moveStep = 0;
19     while (true)
20     {
21         if (x[direction] == 0) // visit y axis
22         candidateNum = row - visitedRows;
23         else // visit x axis
24         candidateNum = col - visitedCols;
25
26         if (candidateNum <= 0)
27         break;
28         result.push_back(matrix[starty][startx]);
29         moveStep++;
30         if (candidateNum == moveStep) // change direction
31         {
32             visitedRows += x[direction] == 0 ? 0 : 1;
33             visitedCols += y[direction] == 0 ? 0 : 1;
34             direction = (direction + 1) % 4;
35             moveStep = 0;
36         }
37         startx += x[direction];
38         starty += y[direction];
39     }
40     return result;
41 }```