LeetCode 面试题 16.22. 兰顿蚂蚁
题目描述
题意分析
无限网格初始全白，蚂蚁从原点朝右出发。每步根据当前格的原颜色转向：白格右转、黑格左转，同时翻转当前格颜色，再沿新方向移动一格。模拟
K步后，输出包含蚂蚁走过的所有格子和最终位置的最小矩形，而不只是包围最终黑格。
解法：黑格集合 + 足迹边界
核心思路
[!blue]
用集合
black只记录当前为黑色的坐标，其余位置默认白色。每次访问当前格，若它在集合中就删除，表示黑变白；否则加入，表示白变黑。这个集合恰好保存每一步后的颜色状态，无需为无限网格预先分配数组。方向按上、右、下、左编码为
0..3，右转是加 1，左转是加 3，再对 4 取模。行坐标向下增加，列坐标向右增加，转向后按dr[dir]、dc[dir]移动。颜色判断必须发生在当前位置，不能先移动到下一格再决定这一轮怎么转。从原点开始记录行列的最小值和最大值，每次移动后把新位置纳入边界。即使某个旧足迹后来变回白色，也不能缩掉这部分边界，因为题目要求包含全部走过的格子。四个极值恰好确定满足要求的最小矩形。
坐标可能为负，模拟阶段直接按有符号坐标保存即可。Java 将行、列分别放入
long的高低 32 位，列先保留低 32 位，避免负列的符号位干扰行；Go 使用行列二元组作键。输出时统一减去最小行列坐标，把所有位置平移到合法数组下标。最后先用
_填充矩形，再把集合中的位置写成X，最后覆盖蚂蚁当前位置的朝向字符。这样按最终颜色生成网格，并让蚂蚁所在格按题目要求显示方向。
解题步骤
- 初始化原点坐标、朝右方向、空黑格集合，以及都为零的四个边界。
- 每步检查当前格颜色，完成对应转向并翻转其集合状态。
- 向新方向移动一格，更新足迹的行列极值。
- 用
maxR - minR + 1、maxC - minC + 1确定输出尺寸，按平移后的下标写入颜色和蚂蚁方向。- 将每行转为字符串返回。
K = 0时边界仍只有原点，结果只包含朝右字符。
代码实现
class Solution {
public List<String> printKMoves(int K) {
int[] dr = {
-1,
0,
1,
0
};
int[] dc = {
0,
1,
0,
-1
};
char[] dirChar = {
'U',
'R',
'D',
'L'
};
Set<Long> black = new HashSet<>();
int r = 0;
int c = 0;
// 方向按上右下左排列，下标一表示初始朝右。
int dir = 1;
int minR = 0;
int maxR = 0;
int minC = 0;
int maxC = 0;
for (int step = 0; step < K; step++) {
long key = (((long) r) << 32) ^ (c & 0xffffffffL);
if (black.contains(key)) {
dir = (dir + 3) % 4;
black.remove(key);
} else {
dir = (dir + 1) % 4;
black.add(key);
}
// 按刚完成的转向移动，再将新位置纳入全部足迹边界。
r += dr[dir];
c += dc[dir];
minR = Math.min(minR, r);
maxR = Math.max(maxR, r);
minC = Math.min(minC, c);
maxC = Math.max(maxC, c);
}
int rows = maxR - minR + 1;
int cols = maxC - minC + 1;
char[][] grid = new char[rows][cols];
for (int i = 0; i < rows; i++) {
Arrays.fill(grid[i], '_');
}
for (long key : black) {
int br = (int) (key >> 32);
int bc = (int) key;
grid[br - minR][bc - minC] = 'X';
}
// 最后写蚂蚁朝向，覆盖当前格原本的颜色。
grid[r - minR][c - minC] = dirChar[dir];
List<String> answer = new ArrayList<>();
for (int i = 0; i < rows; i++) {
answer.add(new String(grid[i]));
}
return answer;
}
}
func printKMoves(K int) []string {
dr := []int{
-1,
0,
1,
0,
}
dc := []int{
0,
1,
0,
-1,
}
dirChar := []byte{
'U',
'R',
'D',
'L',
}
type Point struct{ r, c int }
black := make(map[Point]bool)
// 方向按上右下左排列，下标一表示初始朝右。
r, c, dir := 0, 0, 1
minR, maxR, minC, maxC := 0, 0, 0, 0
for step := 0; step < K; step++ {
p := Point{r: r, c: c}
if black[p] {
dir = (dir + 3) % 4
delete(black, p)
} else {
dir = (dir + 1) % 4
black[p] = true
}
// 按刚完成的转向移动，再将新位置纳入全部足迹边界。
r += dr[dir]
c += dc[dir]
if r < minR {
minR = r
}
if r > maxR {
maxR = r
}
if c < minC {
minC = c
}
if c > maxC {
maxC = c
}
}
rows := maxR - minR + 1
cols := maxC - minC + 1
grid := make([][]byte, rows)
for i := 0; i < rows; i++ {
grid[i] = make([]byte, cols)
for j := 0; j < cols; j++ {
grid[i][j] = '_'
}
}
for p := range black {
grid[p.r-minR][p.c-minC] = 'X'
}
// 最后写蚂蚁朝向，覆盖当前格原本的颜色。
grid[r-minR][c-minC] = dirChar[dir]
answer := make([]string, rows)
for i := 0; i < rows; i++ {
answer[i] = string(grid[i])
}
return answer
}
复杂度分析
- 时间复杂度：期望 $O(K+A)$，其中
A是最终包围矩形面积。模拟每步做常数次集合操作，生成输出还需遍历整个矩形。- 空间复杂度：$O(K+A)$。黑格数量最多与步数同阶，输出网格占
A个格子。
关键点总结
[!green]
- 集合记录当前颜色，四个边界记录全部历史足迹，两者用途不同。
- 每步先依据旧颜色转向并翻色，再移动，使用的是新方向。
- 起点和最终位置都属于输出范围，蚂蚁字符最后覆盖颜色。
易错点总结
[!yellow]
- 黑格翻白时必须从集合删除，否则后续转向和最终颜色都会出错。
- 只按最终黑格确定边框，会漏掉变回白色的历史足迹或最终蚂蚁位置。
- 矩形尺寸要加 1，行列最小值和最大值对应的位置都要包含。
- 负坐标不能直接作数组下标，输出时必须减去最小坐标。
- 若先画蚂蚁再画黑格，当前位置的方向字符可能被覆盖。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 874. 模拟行走机器人 | 中等 | 同样维护无限网格上的位置与朝向，本题格子颜色动态影响转向，原题由指令和静态障碍决定。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！