题目链接
一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。
(1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。
(2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。
编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。
网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由 'X' 表示，白色方格由 '_' 表示，蚂蚁所在的位置由 'L', 'U', 'R', 'D' 表示，分别表示蚂蚁 左、上、右、下 的朝向。只需要返回能够包含蚂蚁走过的所有方格的最小矩形。
示例 1：
输入：0
输出：["R"]示例 2：
输入：2
输出：
["_X","LX"
]示例 3：
输入：5
输出：
["_U","X_","XX"
]说明：
K <= 100000
思路解析（稀疏存储 + 模拟 + 动态边界）
1. 为什么不能开一个“大棋盘”？
- 蚂蚁在无限网格上走，K 最多 1e5。
- 如果直接开一个
grid[200001][200001]之类的二维数组，空间完全爆炸。 - 但实际上，每一步只会翻转当前一个格子的颜色，大部分格子仍是白色。
结论：
只需要记录“黑色格子”的集合，白色格子默认存在但不存储。
2. 状态设计
我们需要维护：
蚂蚁的位置：
(x, y)- 初始位置可以设为
(0, 0)。
- 初始位置可以设为
蚂蚁的方向：
约定方向编码为：0: 上 (U)1: 右 (R)2: 下 (D)3: 左 (L)
初始方向为 右 ®，即
dir = 1。黑色格子集合：
可以用
unordered_set<long long>存储，每个格子坐标(x, y)编码成一个long long：auto encode = [](int x, int y) -> unsigned long long { return ((unsigned long long)(unsigned int)x << 32) | (unsigned long long)(unsigned int)y; };这样就可以 O(1) 平均时间判断一个格子是否是黑色。
注意 int 符号拓展的问题。
已访问区域的最小矩形边界：
minX, maxX, minY, maxY- 每次蚂蚁“站在某个格子上”时，把这个格子纳入边界中：
- 模拟过程中：每一步操作前，将当前
(x, y)更新到边界； - 模拟结束后，再把“最终位置”也更新到边界。
- 模拟过程中：每一步操作前，将当前
题目中要求返回能包含蚂蚁走过所有方格的最小矩形，用这个四元组就可以定位最终输出的矩形大小。
3. 每一步如何模拟？
当前蚂蚁在 (x, y)，方向为 dir：
看当前格子颜色：
- 如果不在黑色集合中：它是 白色
- 如果在黑色集合中：它是 黑色
如果是白色：
- 把它翻成黑色：把
(x, y)加入集合 - 右转：
dir = (dir + 1) % 4
- 把它翻成黑色：把
如果是黑色：
- 把它翻成白色：把
(x, y)从集合中删掉 - 左转：
dir = (dir + 3) % 4（相当于 -1，注意要加 4 再取模或直接 +3 再模）
- 把它翻成白色：把
按新的方向前进一步：
/* 顺时针方向：0 = 上, 1 = 右, 2 = 下, 3 = 左 +----+----+----+----+ | \ | y0 | y1 | y2 | +----+----+----+----+ | x0 | | | | +----+----+----+----+ | x1 | | | | +----+----+----+----+ | x2 | | | | +----+----+----+----+ */ int dx[4] = {-1, 0, 1, 0}; int dy[4] = {0, 1, 0, -1};
循环执行 K 次即可。
4. 如何构造最后的输出网格？
我们现在有：
- 黑色格子集合
black - 蚂蚁最终位置
(x, y)& 方向dir - 覆盖所有走过格子的边界
minX, maxX, minY, maxY
构造网格：
网格的高度/宽度：
int rows = maxX - minX + 1; int cols = maxY - minY + 1;初始化为全白
'_'：vector<string> res(rows, string(cols, '_'));把所有黑色格子标成
'X'for(auto &key : black) { int bx = (int)(key >> 32); int by = (int)(key & 0xffffffff); res[bx - minX][by - minY] = 'X'; }遍历黑色集合中的每个
(bx, by)，在ans[row][col] = 'X'。最后填蚂蚁所在的位置，覆盖之前可能填的
'X'：res[x - minX][y - minY] = "URDL"[dir];
C++ 代码
class Solution {
public:
vector<string> printKMoves(int K) {// 把 (x,y) 编码成一个 unsigned long long// 先将 int:x,y 转换为 unsigned int 避免有符号数符号拓展污染高位auto encode = [](int x, int y) -> unsigned long long{return ((unsigned long long)(unsigned int)x << 32) ^ (unsigned long long)(unsigned int)y;};// 用 hash set 存黑色格子（白色默认不存）unordered_set<unsigned long long> black;black.reserve(K * 2); // 预留两倍空间减少扩容次数// 方向：0 = 上, 1 = 右, 2 = 下, 3 = 左// (0,0) -----> x轴// |// |// ↓// y轴int dx[4] = {0, 1, 0, -1};int dy[4] = {-1, 0, 1, 0};int x = 0, y = 0; // 当前位置int dir = 1; // 初始向右// 边界（用来计算最终矩形大小）int minX = 0, maxX = 0;int minY = 0, maxY = 0;// 模拟 K 步for (int i = 0; i < K; ++i) {unsigned long long key = encode(x, y);bool isBlack = (black.count(key) > 0);if (isBlack) {// 黑色：变白 + 左转black.erase(key);dir = (dir - 1 + 4) % 4; // +4 避免出现负数} else {// 白色：变黑 + 右转black.insert(key);dir = (dir + 1) % 4;}// 前进x += dx[dir];y += dy[dir];minX = min(minX, x);maxX = max(maxX, x);minY = min(minY, y);maxY = max(maxY, y);}int rows = maxY - minY + 1;int cols = maxX - minX + 1;// 创建全白画布vector<string> ans(rows, string(cols, '_'));// 填黑格子for (auto &key : black) {int bx = (int)(key >> 32);int by = (int)(key & 0xffffffff);int row = by - minY; // y 对应行int col = bx - minX; // x 对应列ans[row][col] = 'X';}// 放蚂蚁ans[y - minY][x - minX] = "URDL"[dir];return ans;}};时间 & 空间复杂度分析
设步数为 K，最终最小矩形为 rows × cols：
模拟过程：
- 每一步只做：
- 在 hash 表中插入/删除/查询一次（均摊 O(1)）
- 若干常数操作
- 总时间：O(K)（均摊）
- 每一步只做：
构造输出网格：
- 初始化网格：O(rows × cols)
- 填黑色格子：至多访问
black.size()个格子，black.size() ≤ K，所以 O(K) - 综合：O(rows × cols + K)
在这道题给定的数据范围下，Langton 蚂蚁实际走过区域的面积相对 K 是线性的量级，因此整体时间可以认为是 O(K)。
- 空间复杂度：
- 黑色格子集合：最多 K 个位置 → O(K)
- 输出网格：O(rows × cols)，在本题约为 O(K)
- 综合空间复杂度：O(K)