LeetCode

2013.12.21 01:54

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

Solution:

　　Still spiral order traversal of an m X n matrix, please see "LeetCode - Spiral Matrix" for more detail.

　　Time complexity is O(m * n), space complexity is O(1).

Accepted code:

 1 // 4CE, 2RE, 1AC, such a terrible record..
 2 class Solution {
 3 public:
 4     vector<vector<int> > generateMatrix(int n) {
 5         // IMPORTANT: Please reset any member data you declared, as
 6         // the same Solution instance will be reused for each test case.
 7         
 8         int i, j;
 9         // 1CE here, declaration for int i is missing
10         for(i = 0; i < result.size(); ++i){
11             result[i].clear();
12         }
13         result.clear();
14         
15         // 1RE here, special treatment for 0
16         if(n <= 0){
17             return result;
18         }
19         
20         for(i = 0; i < n; ++i){
21             result.push_back(vector<int>());
22             for(j = 0; j < n; ++j){
23                 result[i].push_back(0);
24             }
25         }
26         
27         // 1CE here, declaration of d is missing
28         int d, x, y, x1, y1, nn;
29         nn = 1;
30         x = 0;
31         y = 0;
32         d = RIGHT;
33         while(true){
34             result[x][y] = nn++;
35             // 1RE here, judge statement should be put after nn++;
36             if(nn > n * n){
37                 break;
38             }
39             while(true){
40                 x1 = x + dir[d][0];
41                 y1 = y + dir[d][1];
42                 if(x1 < 0 || x1 > n - 1 || y1 < 0 || y1 > n - 1 || result[x1][y1] > 0){
43                     // already assigned
44                     d = (d + 1) % 4;
45                 }else{
46                     x = x1;
47                     y = y1;
48                     break;
49                 }
50             }
51         }
52         
53         return result;
54     }
55 private:
56     const int RIGHT = 0;
57     const int DOWN = 1;
58     const int LEFT = 2;
59     const int UP = 3;
60     int dir[4][2] = {
61         // 1CE here, SBC case problem with comma...
62         {0, 1}, {1, 0}, {0, -1}, {-1, 0}
63     };// 1CE here, semicolon missing
64     vector<vector<int>> result;
65 };