难度: Medium
一只蚂蚁坐在由白色和黑色方格构成的无限网格上。开始时，网格全白，蚂蚁面向右侧。每行走一步，蚂蚁执行以下操作。
(1) 如果在白色方格上，则翻转方格的颜色，向右(顺时针)转 90 度，并向前移动一个单位。
(2) 如果在黑色方格上，则翻转方格的颜色，向左(逆时针方向)转 90 度，并向前移动一个单位。
编写程序来模拟蚂蚁执行的前 K 个动作，并返回最终的网格。
网格由数组表示，每个元素是一个字符串，代表网格中的一行，黑色方格由 'X' 表示，白色方格由 '_' 表示，蚂蚁所在的位置由 'L', 'U', 'R', 'D' 表示，分别表示蚂蚁 左、上、右、下 的朝向。只需要返回能够包含蚂蚁走过的所有方格的最小矩形。
示例 1:
输入: 0 输出: ["R"]
示例 2:
输入: 2 输出: [ "_X", "LX" ]
示例 3:
输入: 5 输出: [ "_U", "X_", "XX" ]
说明：
K <= 100000运行时间: 123 ms
内存: 49.4 MB
class Solution:
def printKMoves(self, K: int) -> List[str]:
# dirs = [(0,1), (1,0), (0,-1), (-1,0)]
# x, y = 2000, 2000
# minx, maxx, miny, maxy = x, x, y, y
# table = [[0] * 3000 for _ in range(3000)]
# pos = ['R', 'D', 'L', 'U']
# board = ['_', 'X']
# res, p = [], 0
# for i in range(K):
# d = 1
# if table[x][y]: d = 3
# table[x][y] ^= 1
# p = (p + d) % 4
# x += dirs[p][0]
# y += dirs[p][1]
# minx, maxx, miny, maxy = min(minx, x), max(maxx, x), min(miny, y), max(maxy, y)
# for i in range(minx, maxx + 1):
# temp = ''
# for j in range(miny, maxy + 1):
# if i == x and j == y: temp += pos[p]
# else: temp += board[table[i][j]]
# res.append(temp)
# return res
maps = collections.defaultdict(dict)
x,y,maxX,maxY,minX,minY=0,0,0,0,0,0
pos, p = ['L','U','R','D'],2
move=[[0,-1],[-1,0],[0,1],[1,0]]
maps[0][0]='_'
for _ in range(K):
if y in maps[x] and maps[x][y] == 'X':
maps[x][y] = '_'
p = (p-1)%4
else:
maps[x][y] = 'X'
p = (p+1)%4
x,y=x+move[p][0],y+move[p][1]
if x > maxX:
maxX = x
if x < minX:
minX = x
if y > maxY:
maxY = y
if y < minY:
minY = y
ans=[['_']*(maxY-minY+1) for _ in range(maxX-minX+1)]
for X in maps:
for Y in maps[X]:
ans[X-minX][Y-minY] = maps[X][Y]
ans[x-minX][y-minY]=pos[p]
for i in range(maxX-minX+1):
ans[i]=''.join(ans[i])
return ans
本题解使用字典来动态存储蚂蚁行走路径上的网格状态，以处理无限网格的问题。键为网格的x坐标，值为另一个字典，其键为y坐标，值为该位置的颜色状态('X'或'_')。蚂蚁的移动方向用列表pos定义，并用整数p管理当前方向的索引。蚂蚁移动的逻辑是，根据当前所在格子的颜色决定转向方向并翻转颜色，然后根据新方向移动到下一个格子。同时记录蚂蚁遍历过的网格的最大和最小x、y坐标，用于最后构建最小包含蚂蚁路径的矩形网格。
时间复杂度: O(K)
空间复杂度: O(K)
import collections
class Solution:
def printKMoves(self, K: int) -> List[str]:
maps = collections.defaultdict(dict) # 使用字典存储网格状态
x, y, maxX, maxY, minX, minY = 0, 0, 0, 0, 0, 0 # 初始化蚂蚁位置和边界
pos, p = ['L','U','R','D'], 2 # pos用于定位蚂蚁的朝向
move = [[0,-1],[-1,0],[0,1],[1,0]] # 移动方向的向量表示
maps[0][0] = '_' # 初始位置为白格
for _ in range(K):
if y in maps[x] and maps[x][y] == 'X':
maps[x][y] = '_' # 翻转为白格
p = (p-1) % 4 # 向左转
else:
maps[x][y] = 'X' # 翻转为黑格
p = (p+1) % 4 # 向右转
x, y = x + move[p][0], y + move[p][1] # 移动到新位置
maxX, maxY, minX, minY = max(maxX, x), max(maxY, y), min(minX, x), min(minY, y) # 更新边界
ans = [['_'] * (maxY - minY + 1) for _ in range(maxX - minX + 1)] # 创建最终的网格
for X in maps:
for Y in maps[X]:
ans[X - minX][Y - minY] = maps[X][Y] # 填充网格颜色
ans[x - minX][y - minY] = pos[p] # 标记蚂蚁的当前位置和朝向
for i in range(maxX - minX + 1):
ans[i] = ''.join(ans[i]) # 将网格行转换为字符串
return ans # 返回结果
使用defaultdict的优势在于它可以自动初始化为一个空的字典，当尝试访问一个不存在的键时，不会引发错误，而是自动创建该键并赋予一个默认值（本题中为另一个字典）。这使得代码在处理无限网格时更加灵活和简洁，避免了复杂的存在性检查和初始化逻辑。对于兰顿蚂蚁这类问题，这一特性极大地简化了动态网格状态的管理。
在每次迭代中，通过检查蚂蚁当前所在格子的颜色来决定其转向。如果蚂蚁在黑格（'X'），则向左转（p减1模4），若在白格（'_'），则向右转（p加1模4）。更新朝向后，根据`pos`列表中的朝向和`move`数组中对应的向量来更新蚂蚁的坐标。这种方法确保了蚂蚁的方向和位置始终正确同步更新，从而正确模拟蚂蚁的移动规则。
方向数组`pos`用于表示蚂蚁的朝向（'L', 'U', 'R', 'D'），对应左、上、右、下四个方向。移动向量`move`是一个二维列表，其中每个子列表代表相应方向的坐标偏移量。例如，向左（'L'）对应的偏移量是[0, -1]，表示x坐标不变，y坐标减1。在蚂蚁的每一步移动中，首先根据当前的格子颜色更新`pos`中的朝向索引p，然后使用`move[p]`获取对应的坐标偏移，从而更新蚂蚁的位置。这种设计方式使得朝向和移动逻辑清晰、紧密地结合在一起，保证了蚂蚁的行为正确无误。