-
-
Notifications
You must be signed in to change notification settings - Fork 299
/
885.cpp
107 lines (100 loc) · 3.41 KB
/
885.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
__________________________________________________________________________________________________
sample 56 ms submission
class Solution {
vector<vector<int>> spiralImitate (int R, int C, int r0, int c0) {
vector<vector<int>> ret;
/***
* direction of the move:
* east, down, west, up
*/
int dir = 0;
/* boundary of visited cells, inclusive */
int rlow = r0, rhigh = r0;
int clow = c0, chigh = c0;
while (!(rlow == -1 && rhigh == R &&
clow == -1 && chigh == C)) {
dir %= 4;
switch (dir) {
/* move east */
case 0:
for (int j = max (0, clow); rlow > -1 && j <= min(chigh, C - 1); j++) {
ret.push_back ({rlow, j});
}
/* chigh at most C */
if (chigh < C) {
chigh++;
}
dir++;
break;
case 1:
for (int i = max (0, rlow); chigh < C && i <= min(rhigh, R - 1); i++) {
ret.push_back ({i, chigh});
}
if (rhigh < R) {
rhigh++;
}
dir++;
break;
case 2:
for (int j = min (C - 1, chigh); rhigh < R && j >= max(clow, 0); j--) {
ret.push_back ({rhigh, j});
}
if (clow > -1) {
clow--;
}
dir++;
break;
case 3:
for (int i = min (rhigh, R - 1); clow > -1 && i >= max(0, rlow); i--) {
ret.push_back ({i, clow});
}
if (rlow > -1) {
rlow--;
}
dir++;
break;
}
}
return ret;
}
public:
vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
return spiralImitate (R, C, r0, c0);
}
};
__________________________________________________________________________________________________
sample 12592 kb submission
static int fast_io = []() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}();
class Solution {
public:
vector<vector<int>> spiralMatrixIII(int R, int C, int r0, int c0) {
int dir = 0, steps = 1, dist = 1, count = C * R;
vector<vector<int>> spiral;
spiral.reserve(count);
while (spiral.size() < count) {
if (r0 >= 0 &&
r0 < R &&
c0 >= 0 &&
c0 < C) {
spiral.emplace_back(initializer_list<int>{r0, c0});
}
if (dir == 0) ++c0;
else if (dir == 1) ++r0;
else if (dir == 2) --c0;
else --r0;
--steps;
if (steps == 0) {
if (dir % 2 == 1) ++dist;
steps = dist;
++dir;
if (dir == 4) dir = 0;
}
}
return spiral;
}
};
__________________________________________________________________________________________________