机器人房间清扫
Robot Room Cleaner
题目详情
问题：机器人房间清扫
考察：回溯、交互
来源：DSA Prep / Citadel
链接：https://leetcode.com/problems/robot-room-cleaner
英文原题
Problem: Robot Room Cleaner
Patterns: Backtracking, Interactive
Recency: 2yr
Link: https://leetcode.com/problems/robot-room-cleaner
Source: https://www.dsaprep.dev/blog/citadel-coding-interview-questions/
解析
思路：在未知地图上做 DFS 回溯。记录相对坐标 visited，每次尝试四个方向；若能前进就递归清扫，返回时执行转身、前进、转身恢复原位置和朝向。
复杂度：每个可达格子访问一次，时间 O(R)，空间 O(R)。
英文解析
Approach: Treat the unknown room as a graph and run DFS with coordinates relative to the start. After exploring a direction, issue the inverse movement sequence to backtrack the robot to the previous cell and orientation.
Complexity: Visits each reachable cell once; space is for reachable cells.