1
class Solution {
2
 public:
3
  vector<int> _res;
4
  vector<vector<bool>> _visited;
5

6
  void spin(vector<vector<int>> &matrix, int direction, int i, int j) {
7
    _visited[i][j] = true;
8
    _res.push_back(matrix[i][j]);
9

10
    switch (direction) {
11
      // left to right
12
      case 0:
13
        if (j + 1 >= matrix[0].size() || _visited[i][j + 1]) {
14
          direction = 1;
15
          i++;
16
        } else {
17
          j++;
18
        }
19
        break;
20
      // up to bottom
21
      case 1:
22
        if (i + 1 >= matrix.size() || _visited[i + 1][j]) {
23
          direction = 2;
24
          j--;
25
        } else {
26
          i++;
27
        }
28
        break;
29
      // right to left
30
      case 2:
31
        if (j == 0 || _visited[i][j - 1]) {
32
          direction = 3;
33
          i--;
34
        } else {
35
          j--;
36
        }
37
        break;
38
      // bottom to up
39
      case 3:
40
        if (i == 0 || _visited[i - 1][j]) {
41
          direction = 0;
42
          j++;
43
        } else {
44
          i--;
45
        }
46
        break;
47
    }
48
    if (i < 0 || i >= matrix.size() || j < 0 || j >= matrix[0].size()) {
49
      return;
50
    }
51
    if (_visited[i][j]) {
52
      return;
53
    }
54
    spin(matrix, direction, i, j);
55
  }
56

57
  vector<int> spiralOrder(vector<vector<int>> &matrix) {
58
    _res.clear();
59
    _visited = vector<vector<bool>>(matrix.size(), std::vector<bool>(matrix[0].size(), false));
60
    spin(matrix, 0, 0, 0);
61
    return _res;
62
  }
63
};