题目
一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时,网格全白,蚂蚁面向右侧。每行走一步,蚂蚁执行以下操作。
(1) 如果在白色方格上,则翻转方格的颜色,向右(顺时针)转 90 度,并向前移动一个单位。
(2) 如果在黑色方格上,则翻转方格的颜色,向左(逆时针方向)转 90 度,并向前移动一个单位。
编写程序来模拟蚂蚁执行的前 K 个动作,并返回最终的网格。
网格由数组表示,每个元素是一个字符串,代表网格中的一行,黑色方格由 'X'
表示,白色方格由 '_'
表示,蚂蚁所在的位置由 'L'
, 'U'
, 'R'
, 'D'
表示,分别表示蚂蚁 左、上、右、下 的朝向。只需要返回能够包含蚂蚁走过的所有方格的最小矩形。
示例 1:
输入: 0
输出: ["R"]
1
2
2
示例 2:
输入: 2
输出:
[
"_X",
"LX"
]
1
2
3
4
5
6
2
3
4
5
6
示例 3:
输入: 5
输出:
[
"_U",
"X_",
"XX"
]
1
2
3
4
5
6
7
2
3
4
5
6
7
说明:
K <= 100000
题解
java
enum BlockColor {
/**
* 黑色块
*/
BLACK("X") {
@Override
BlockColor overturn() {
return WHITE;
}
},
/**
* 白色块
*/
WHITE("_") {
@Override
BlockColor overturn() {
return BLACK;
}
};
String color;
BlockColor(String color) {
this.color = color;
}
/**
* 方格翻转
* @return {@link BlockColor}
*/
abstract BlockColor overturn();
}
enum AntDirection {
/**
* 蚂蚁左朝向
*/
LEFT('L') {
@Override
void moveClockwise(Meta meta) {
meta.row--;
meta.antDirection = UP;
}
@Override
void moveAnticlockwise(Meta meta) {
meta.row++;
meta.antDirection = DOWN;
}
},
/**
* 上
*/
UP('U') {
@Override
void moveClockwise(Meta meta) {
meta.column++;
meta.antDirection = RIGHT;
}
@Override
void moveAnticlockwise(Meta meta) {
meta.column--;
meta.antDirection = LEFT;
}
},
/**
* 右
*/
RIGHT('R') {
@Override
void moveClockwise(Meta meta) {
meta.row++;
meta.antDirection = DOWN;
}
@Override
void moveAnticlockwise(Meta meta) {
meta.row--;
meta.antDirection = UP;
}
},
/**
* 下
*/
DOWN('D') {
@Override
void moveClockwise(Meta meta) {
meta.column--;
meta.antDirection = LEFT;
}
@Override
void moveAnticlockwise(Meta meta) {
meta.column++;
meta.antDirection = RIGHT;
}
};
char direction;
AntDirection(char direction) {
this.direction = direction;
}
void move(Meta meta) {
// 当前块白色顺时针移动
if (meta.blockColor == BlockColor.WHITE) {
this.moveClockwise(meta);
} else {
// 当前块为黑色逆时针移动
this.moveAnticlockwise(meta);
}
}
/**
* 顺时针移动
*/
abstract void moveClockwise(Meta meta);
/**
* 逆时针移动
*/
abstract void moveAnticlockwise(Meta meta);
}
static class Meta {
// 方块颜色哈希缓存
Map<Integer, Map<Integer, BlockColor>> paths = new HashMap<>(8);
// 初始方向
AntDirection antDirection = AntDirection.RIGHT;
BlockColor blockColor;
// 当前所在行列位置
int row = 0, column = 0;
// 行列最大最小值
int minRow = 0, maxRow = 0, minColumn = 0, maxColumn = 0;
Meta() {
// 初始化至少一行
paths.put(0, new HashMap<>());
}
void move() {
// 当前块颜色
BlockColor color = paths.getOrDefault(this.row, new HashMap<>(4)).getOrDefault(column, BlockColor.WHITE);
this.blockColor = color;
paths.merge(this.row, new HashMap<>(4), (o, n) -> o);
paths.get(this.row).put(this.column, color.overturn());
// 前进
this.antDirection.move(this);
// 更新行列最大值
this.minRow = Integer.min(this.row, this.minRow);
this.maxRow = Integer.max(this.row, this.maxRow);
this.minColumn = Integer.min(this.column, this.minColumn);
this.maxColumn = Integer.max(this.column, this.maxColumn);
}
List<String> result() {
// 行字符个数
int width = this.maxColumn - this.minColumn + 1;
List<String> collect =
IntStream.rangeClosed(this.minRow, this.maxRow)
.mapToObj(row ->
Optional.ofNullable(this.paths.get(row))
.filter(it -> !it.isEmpty())
.map(columns ->
IntStream.rangeClosed(this.minColumn, this.maxColumn)
.mapToObj(column ->
Optional.ofNullable(columns.get(column))
.map(it -> it.color)
.orElse(BlockColor.WHITE.color)
)
.collect(Collectors.joining(""))
)
.orElseGet(() -> String.join("", Collections.nCopies(width, BlockColor.WHITE.color)))
)
.collect(Collectors.toList());
// 将当前行列位置替换为方向
int replaceRow = this.row - this.minRow;
StringBuilder sb = new StringBuilder(collect.get(replaceRow));
sb.setCharAt(this.column - this.minColumn, this.antDirection.direction);
collect.set(replaceRow, sb.toString());
return collect;
}
}
public List<String> printKMoves(int K) {
Meta meta = new Meta();
while (K > 0) {
meta.move();
K--;
}
return meta.result();
}
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198