机器人房间清扫

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)。