LeetCode 面试题 16.22. 兰顿蚂蚁
目录
题目描述
题意分析
一只蚂蚁站在无限大的网格上，网格初始全白，蚂蚁初始面向右侧。每一步的规则是：站在白格上就把它翻成黑、顺时针（向右）转 90 度、前进一格；站在黑格上就把它翻成白、逆时针（向左）转 90 度、前进一格。要求模拟前
K步，返回最终棋盘。
输出格式里藏着三个必须逐字对齐的约定。第一，黑格用
'X'、白格用'_'。第二，蚂蚁所在位置用'L'、'U'、'R'、'D'表示它当前的朝向（左、上、右、下），并且这个字符会覆盖该格原本的颜色。第三，只返回能包含蚂蚁走过的所有格子的最小矩形——不是固定尺寸，也不是黑格的包围盒，而是蚂蚁足迹（含起点和终点）的包围盒。
约束里最关键的信号是"无限大网格"：不能开固定大小的二维数组，因为蚂蚁可能往任意方向走出任意远；坐标可以是负数。同时
K有上界（题目给到 $10^5$ 量级），所以蚂蚁最多访问K + 1个格子，黑格数量也不超过这个量级——用哈希集合只记录黑格就够了，白格是默认状态不必存储。
边界上要覆盖：
K = 0（一步不走，输出只有起点一格，内容是蚂蚁初始朝向'R'）；蚂蚁走回已经变黑的格子（要翻回白色并从集合里删除）；蚂蚁终点恰好落在黑格上（此时输出朝向字符而不是'X'）；以及包围盒要包含起点(0, 0)。
解法：模拟 + 哈希集合（记录黑格子）
核心思路
这题没有可优化的算法结构——蚂蚁的轨迹是混沌的，第
K步的位置无法用公式跳算，只能老老实实模拟K步。所以难点全在用什么数据结构承载"无限网格"，以及如何在模拟过程中顺便算出输出所需的信息。
第一个观察：网格初始全白，任何时刻黑格的数量都不超过蚂蚁走过的步数。所以不需要存整个网格，只需要一个集合
black记录"哪些坐标当前是黑的"，不在集合里就是白的。翻转颜色变成集合的插入/删除，判断颜色变成一次集合查询，都是 $O(1)$。这就是"稀疏状态用哈希、稠密状态用数组"的典型应用。
第二个观察：输出要的最小矩形，取决于蚂蚁走过的所有格子的坐标极值。这些极值不需要事后遍历集合去求——集合里只有黑格，而白格足迹（被翻回白色的格子）同样属于"走过的格子"，漏掉它们包围盒就会偏小。正确做法是在模拟过程中，每移动一步就用新坐标更新
minR、maxR、minC、maxC，并把它们初始化为起点(0, 0)，这样起点和终点都天然被包含。
由此确定状态与不变量：
(r, c)是蚂蚁当前坐标，dir是当前朝向的编号，black恒等于"当前为黑色的格子集合"，四个极值恒等于"到目前为止蚂蚁访问过的所有坐标（含起点）的边界"。每一步先按当前格颜色更新dir和black，再按新的dir前进并更新极值，不变量即被保持。
方向的编码是这题最容易翻车的地方。把四个方向按顺时针顺序排成数组
U, R, D, L（下标 0..3），对应的行列增量是dr = {-1, 0, 1, 0}、dc = {0, 1, 0, -1}（行号向下增大，所以"上"是-1）。这样右转就是dir = (dir + 1) % 4，左转就是dir = (dir + 3) % 4（等价于-1后取模，但避免了负数取模）。蚂蚁初始面向右，所以dir的初值是1而不是0——这个初值若写错，全部用例的输出都会整体旋转 90 度。
最后是坐标怎么当哈希键。Java 里把
(r, c)两个 int 打包进一个long：高 32 位放r、低 32 位放c，写成(((long) r) << 32) ^ (c & 0xffffffffL)。c & 0xffffffffL是为了在c为负数时只取它的低 32 位，避免符号扩展污染高位；解包时(int)(key >> 32)取回r、(int) key取回c。这样比用对象做键少一层装箱，性能更好。Go 里直接用结构体Point{r, c}作 map 的键即可，语言天然支持可比较结构体做键。
解题步骤
- 建立方向表并把
dir初始化为1（朝右）。dr/dc/dirChar三个数组的下标必须严格一一对应，任何一个数组的顺序写错都会导致朝向字符与实际移动方向不符。
black初始化为空集合，(r, c)从(0, 0)出发，四个极值全部初始化为0。极值初始化为起点坐标而不是"正负无穷"，是因为起点本身必须被包含进输出矩形——K = 0时这是唯一被包含的格子。
- 循环
K次，每次先判断当前格是否在black中。在集合里（黑格）就左转并把它从集合中删除（翻白）；不在（白格）就右转并加入集合（翻黑）。删除这一步极易漏掉，漏了之后蚂蚁再次经过时会一直按黑格处理，轨迹从此全错。
- 转向之后再前进。顺序不能颠倒：题目规则明确是"翻转颜色 → 转向 → 前进一格"，所以移动用的必须是转向后的方向。若先移动再转向，第一步就会走错方向。
- 前进后立即更新四个极值。用新坐标去更新，保证每个被踩过的格子都进了包围盒。注意不能只在"翻黑"时更新——被翻回白色的格子同样算走过。
- 循环结束后按
rows = maxR - minR + 1、cols = maxC - minC + 1开二维字符数组，全部填'_'。这一步把稀疏表示还原成稠密输出，尺寸恰好是最小包围矩形。
- 把
black中的每个坐标映射到网格下标[r - minR][c - minC]并写'X'。减去最小值是把可能为负的绝对坐标平移成从 0 开始的数组下标。
- 最后把蚂蚁位置写成
dirChar[dir]。这一步必须放在填完所有'X'之后，因为朝向字符要覆盖颜色；若先写朝向再刷黑格，蚂蚁停在黑格上时会被'X'覆盖掉。
- 逐行拼成字符串返回。
以
K = 2走一遍（起点(0, 0)，dir = 1即朝右）：第 1 步：当前格
(0, 0)不在black中，是白格 → 右转dir = (1 + 1) % 4 = 2（朝下），把(0, 0)加入black。按dir = 2前进：r += 1得到(1, 0)。更新极值：maxR = 1，其余不变。第 2 步：当前格
(1, 0)不在black中，是白格 → 右转dir = (2 + 1) % 4 = 3（朝左），把(1, 0)加入black。按dir = 3前进：c += -1得到(1, -1)。更新极值：minC = -1。输出阶段：
minR = 0、maxR = 1→rows = 2；minC = -1、maxC = 0→cols = 2。网格先全填'_'。刷黑格：(0, 0)映射到[0 - 0][0 + 1] = [0][1]，写'X'；(1, 0)映射到[1][1]，写'X'。最后写蚂蚁：位置(1, -1)映射到[1][0]，dirChar[3] = 'L'。得到
["_X", "LX"]，与题目示例一致。再以
K = 5继续走 3 步（承接上面的状态：(1, -1)，dir = 3，black = {(0,0), (1,0)}）：第 3 步：
(1, -1)是白格 → 右转dir = 0（朝上），加入black。前进r += -1得到(0, -1)。第 4 步：
(0, -1)是白格 → 右转dir = 1（朝右），加入black。前进c += 1得到(0, 0)。第 5 步：
(0, 0)在black中，是黑格 → 左转dir = (1 + 3) % 4 = 0（朝上），把(0, 0)从black中删除（翻回白色）。前进r += -1得到(-1, 0)。更新minR = -1。输出阶段：
minR = -1、maxR = 1→rows = 3；minC = -1、maxC = 0→cols = 2。black = {(1,0), (1,-1), (0,-1)}，映射后分别写在[2][1]、[2][0]、[1][0]。蚂蚁在(-1, 0)映射到[0][1]，写dirChar[0] = 'U'。得到
["_U", "X_", "XX"]，与题目示例一致。注意(0, 0)在第 5 步被翻回白色，所以[1][1]是'_'而不是'X'——这正是"黑格必须从集合中删除"的验证点；同时(0, 0)虽已变白，仍在包围盒内，因为极值是按足迹而非按黑格统计的。最后看
K = 0：一步不走，四个极值都是 0，rows = cols = 1，网格填'_'后写入dirChar[1] = 'R'，返回["R"]，符合题意。
代码实现
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, maxR = 0, minC = 0, 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 + R \cdot C)$。模拟阶段走
K步，每步只做一次哈希查询、一次插入或删除和常数次比较，都是 $O(1)$；输出阶段要初始化并填充R × C的字符网格，再逐行拼成字符串。由于蚂蚁每步最多让包围盒扩大 1，R和C都不超过 $2K + 1$，最坏情况下输出阶段可达 $O(K^2)$，但实际轨迹远比这紧凑。- 空间复杂度：$O(K + R \cdot C)$。
black集合最多存K个坐标（每步至多新增一个黑格）；输出网格占 $O(R \cdot C)$；方向表是常数。
关键点总结
- 无限网格 + 稀疏状态，就用哈希集合只存"非默认值"的格子。白格是默认态不必存储，翻转变成集合的增删。这条规则可以推广：任何"初始全为某个值、只有少量位置被改动"的大空间，都该用哈希而不是数组。
- 输出所需的边界信息要在模拟过程中顺带维护，不要事后重算。本题若事后遍历
black求包围盒，会漏掉被翻回白色的足迹格子，答案偏小。凡是"最后要输出一个范围"的模拟题，都应该在每次状态变化时同步更新极值。- 方向编码要按旋转顺序排列，让转向变成模加法。把
U, R, D, L按顺时针排成环，右转+1、左转+3（而不是-1，避免负数取模），这是所有"转向类"模拟题的标准写法；dr/dc/朝向字符三张表必须严格同序。- 负坐标靠"减去最小值"平移成数组下标。这是把绝对坐标系映射到输出缓冲区的通用手法，和差分数组里减去基准年份是同一个思路。
- 输出层的覆盖顺序要和题意一致。蚂蚁字符覆盖颜色，所以必须最后写；写反了会在"蚂蚁停在黑格上"的用例里出错，而这类用例并不罕见。
- 面试视角：先把规则和输出约定复述一遍再动手。这题的难度不在算法而在"读题是否精确"——初始朝右还是朝上、朝向字符用
URDL还是箭头、包围盒按足迹还是按黑格，任何一处理解偏差都会全盘皆错。开口时把这几条逐一确认，既能避免返工，也向面试官展示了处理规格类需求的严谨度。
易错点总结
- 错误写法：
dir初始化为0（朝上） → 用例K = 0：输出["U"]，正确答案是["R"]；K = 2时整个轨迹逆时针旋转 90 度，输出["X_", "XL"]之类的错误结果。题目明确说蚂蚁初始面向右侧。- 错误写法：朝向字符用
{'^', '>', 'v', '<'}→ 用例K = 0：输出["^"]，正确答案是["R"]。题目规定用'L'、'U'、'R'、'D'四个字母。- 错误写法：踩到黑格时只转向不从集合中删除 → 用例
K = 5：第 5 步经过已变黑的(0, 0)时没有翻回白色，输出的[1][1]是'X'而不是'_'，得到["_U", "XX", "XX"]，正确答案是["_U", "X_", "XX"]；更糟的是蚂蚁后续再经过时颜色判断持续错误，轨迹整体跑偏。- 错误写法：先前进再转向 → 用例
K = 1：蚂蚁按初始的朝右方向走到(0, 1)再转向，输出的位置和朝向都与正解不符。规则顺序是"翻色 → 转向 → 前进"。- 错误写法：左转写成
dir = (dir - 1) % 4→ 用例：dir = 0时踩到黑格：(0 - 1) % 4在 Java/Go 里都是-1，用它当数组下标直接越界抛异常。负数取模要写成(dir + 3) % 4或((dir - 1) % 4 + 4) % 4。- 错误写法：包围盒只按
black集合里的坐标计算 → 用例K = 5：(0, 0)已被翻回白色不在集合中，若按集合求极值会丢掉它对边界的贡献；当足迹恰好在被翻白的格子处达到边界时，输出矩形偏小，行列数直接错。- 错误写法：极值初始化成
Integer.MAX_VALUE/Integer.MIN_VALUE→ 用例K = 0：循环一次都不执行，极值保持在初始的极端值，rows = maxR - minR + 1算出一个巨大的负数或溢出值，开数组时崩溃。必须初始化为起点坐标0。- 错误写法：先写蚂蚁字符再刷黑格 → 用例：蚂蚁终点恰好停在一个黑格上（较长的
K很容易出现）：朝向字符被'X'覆盖，输出里根本找不到蚂蚁。覆盖顺序必须是先颜色后蚂蚁。- 错误写法：Java 里打包坐标写成
((long) r << 32) | c（用或且不掩码） → 用例：c = -1：c会被符号扩展成全 1 的 long，或运算把高 32 位也变成全 1，r的信息被完全冲掉，不同的r映射到同一个键，黑格互相覆盖。必须写c & 0xffffffffL先截断低 32 位。- 错误写法：用
r * 10000 + c之类的算术打包 → 用例：c为负数或|c|超过 10000：不同坐标产生相同的键，或者不同的键无法正确解包。坐标打包要么用位运算精确分段，要么直接用对象/结构体做键。- 错误写法：Go 里
delete(black, p)写成black[p] = false→ 用例K = 5：black[p]读出false判断是对的，但for p := range black遍历时这个键仍在 map 里，会被当成黑格写入'X'。标记为 false 不等于删除，遍历前必须真正delete。- 错误写法：
rows/cols忘记+1→ 用例K = 0：maxR - minR = 0，开出 0 行的数组，随后写grid[0][0]越界。闭区间[minR, maxR]的长度是差值加一。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 289. 生命游戏 | 中等 | 网格有限但要求原地更新，靠位标记同时保存新旧两代状态 |
| 874. 模拟行走机器人 | 中等 | 同样是转向 + 前进，但障碍点集合用哈希，且要记录最远距离平方 |
| 1041. 困于环中的机器人 | 中等 | 不必模拟到底，靠"一轮指令后朝向是否复位"判断轨迹是否有界 |
| LCP 17. 速算机器人 | 简单 | 状态只有两个整数且每步都翻倍，可用不变量直接推出闭式解 |
| 面试题 08.02. 迷路的机器人 | 中等 | 从确定性模拟升级为带回溯与记忆化剪枝的路径搜索 |