难度: Medium
Submission
运行时间: 39 ms
内存: 19.3 MB
class Solution:
def numberOfCleanRooms(self, room: List[List[int]]) -> int:
#模拟题
def move(x,y,tt):
if tt==0:
if 0<=x<m and 0<=y+1<n and room[x][y+1]==0:
return (x,y+1,tt)
else:
return (x,y,(tt+1)%4)
elif tt==1:
if 0<=x+1<m and 0<=y<n and room[x+1][y]==0:
return (x+1,y,tt)
else:
return (x,y,(tt+1)%4)
elif tt==2:
if 0<=x<m and 0<=y-1<n and room[x][y-1]==0:
return (x,y-1,tt)
else:
return (x,y,(tt+1)%4)
else:
if 0<=x-1<m and 0<=y<n and room[x-1][y]==0:
return (x-1,y,tt)
else:
return (x,y,(tt+1)%4)
m,n=len(room),len(room[0])
vis=set()
#模拟这个过程即可
a,b,c=0,0,0
ans=set()
while (a,b,c) not in vis:
vis.add((a,b,c))
ans.add((a,b))
a,b,c=move(a,b,c)
return len(ans)
Explain
这个题解利用模拟行走过程的方式来确定扫地机器人可以清扫的区域。它通过定义一个移动函数 move，根据当前方向和位置来决定下一步的动作。如果下一步的位置是可行走的（即为0），机器人就向该方向移动；否则，它就原地转向。整个过程中，机器人的位置和方向被记录在集合 vis 中以避免重复行动。同时，已清扫的位置被添加到另一个集合 ans 中。最后，函数返回 ans 集合的大小，即不重复的清扫过的格子数量。
时间复杂度: O(m * n)
空间复杂度: O(m * n)
class Solution:
def numberOfCleanRooms(self, room: List[List[int]]) -> int:
# 定义移动函数，处理机器人的移动逻辑
def move(x, y, tt):
directions = [
(0, 1), # 向右移动
(1, 0), # 向下移动
(0, -1), # 向左移动
(-1, 0) # 向上移动
]
dx, dy = directions[tt]
nx, ny = x + dx, y + dy
# 检查新位置是否有效
if 0 <= nx < m and 0 <= ny < n and room[nx][ny] == 0:
return (nx, ny, tt)
else:
# 转向
return (x, y, (tt + 1) % 4)
# 房间的行数和列数
m, n = len(room), len(room[0])
vis = set() # 记录已访问的位置和方向
ans = set() # 记录清扫过的位置
a, b, c = 0, 0, 0 # 初始位置和方向
# 主循环直到重复状态发生
while (a, b, c) not in vis:
vis.add((a, b, c))
ans.add((a, b))
a, b, c = move(a, b, c)
return len(ans) # 返回清扫过的不重复格子数
Explore
当机器人尝试移动到一个新位置时，`move` 函数首先会检查这个新位置是否有效，即位置是否在房间的边界内以及该位置是否为0（可行走区域）。如果这个新位置无法行走（比如是非0格子），则机器人不会移动到那个位置，而是保持在当前位置，并且函数会返回当前位置和新的方向，方向通过 `(tt + 1) % 4` 进行计算，表示机器人将顺时针转向下一个方向。
是的，转向规则是机器人会顺时针转向下一个方向。这是通过使用 `(tt + 1) % 4` 实现的，其中 `tt` 是当前方向的索引，通过对4取余数确保方向循环在四个可能的方向（向右、向下、向左、向上）之间。每次机器人遇到不可行进的区域时，都会应用这个规则进行转向。
`tt` 在 `vis` 集合中的 `(x, y, tt)` 元组中代表机器人当前的方向。这个方向是整数索引，对应于机器人可能的四个移动方向（0代表向右，1代表向下，2代表向左，3代表向上）。存储方向是必要的，因为即使在相同的位置 `(x, y)`，不同的方向可能导致不同的后续行为，所以需要记录每一个位置和方向的组合以避免重复行为。
`ans` 集合用来存储机器人已经清扫过的格子的坐标 `(x, y)`。理论上，由于 `ans` 是一个集合，它会自动处理重复的元素，即它不会存储重复的格子。然而，由于 `vis` 集合会阻止机器人重复进入相同位置和方向的状态，实际上机器人不会有机会多次清扫同一个格子。因此，在这种情况下，`ans` 中每个格子都只会被记录一次。