房间中的某个位置上有一个机器人，你需要控制它清扫房间。房间被建模为一个 m x n 的二进制网格，其中 0 表示单元格中有障碍物，1 表示空单元格。
机器人从一个未知的空单元格开始出发，并且你无法访问网格，但你可以使用给定的 API Robot 控制机器人。
你的任务是使用机器人清扫整个房间（即清理房间中的每个空单元格）。机器人具有四个给定的API，可以前进、向左转或向右转。每次转弯 90 度。
当机器人试图移动到一个存在障碍物的单元格时，它的碰撞传感器会检测到障碍物，并停留在当前单元格。
设计一个算法，使用下述 API 清扫整个房间：
interface Robot {
// 若下一个单元格为空，则返回 true ，并移动至该单元格。
// 若下一个单元格为障碍物，则返回 false ，并停留在当前单元格。
boolean move();
// 在调用 turnLeft/turnRight 后机器人会停留在当前单元格。
// 每次转弯 90 度。
void turnLeft();
void turnRight();
// 清理当前单元格。
void clean();
}
注意 扫地机器人的初始方向向上。你可以假定网格的四周都被墙包围。
自定义测试：
输入只用于初始化房间和机器人的位置。你需要「盲解」这个问题。换而言之，你必须在对房间和机器人位置一无所知的情况下，只使用 4 个给出的 API 解决问题。
示例 1：
输入：room = [[1,1,1,1,1,0,1,1],[1,1,1,1,1,0,1,1],[1,0,1,1,1,1,1,1],[0,0,0,1,0,0,0,0],[1,1,1,1,1,1,1,1]], row = 1, col = 3 输出：Robot cleaned all rooms. 解释： 房间内的所有单元格用 0 或 1 填充。 0 表示障碍物，1 表示可以通过。 机器人从 row=1, col=3 的初始位置出发。 在左上角的一行以下，三列以右。
示例 2：
输入：room = [[1]], row = 0, col = 0 输出：Robot cleaned all rooms.
提示：
m == room.lengthn == room[i].length1 <= m <= 1001 <= n <= 200room[i][j]为0或1.0 <= row < m0 <= col < nroom[row][col] == 1- 所有空单元格都可以从起始位置出发访问到。
我们不妨假设机器人的初始位置为
时间复杂度
# """
# This is the robot's control interface.
# You should not implement it, or speculate about its implementation
# """
# class Robot:
# def move(self):
# """
# Returns true if the cell in front is open and robot moves into the cell.
# Returns false if the cell in front is blocked and robot stays in the current cell.
# :rtype bool
# """
#
# def turnLeft(self):
# """
# Robot will stay in the same cell after calling turnLeft/turnRight.
# Each turn will be 90 degrees.
# :rtype void
# """
#
# def turnRight(self):
# """
# Robot will stay in the same cell after calling turnLeft/turnRight.
# Each turn will be 90 degrees.
# :rtype void
# """
#
# def clean(self):
# """
# Clean the current cell.
# :rtype void
# """
class Solution:
def cleanRoom(self, robot):
"""
:type robot: Robot
:rtype: None
"""
def dfs(i, j, d):
vis.add((i, j))
robot.clean()
for k in range(4):
nd = (d + k) % 4
x, y = i + dirs[nd], j + dirs[nd + 1]
if (x, y) not in vis and robot.move():
dfs(x, y, nd)
robot.turnRight()
robot.turnRight()
robot.move()
robot.turnRight()
robot.turnRight()
robot.turnRight()
dirs = (-1, 0, 1, 0, -1)
vis = set()
dfs(0, 0, 0)/**
* // This is the robot's control interface.
* // You should not implement it, or speculate about its implementation
* interface Robot {
* // Returns true if the cell in front is open and robot moves into the cell.
* // Returns false if the cell in front is blocked and robot stays in the current cell.
* public boolean move();
*
* // Robot will stay in the same cell after calling turnLeft/turnRight.
* // Each turn will be 90 degrees.
* public void turnLeft();
* public void turnRight();
*
* // Clean the current cell.
* public void clean();
* }
*/
class Solution {
private int[] dirs = {-1, 0, 1, 0, -1};
private Set<List<Integer>> vis = new HashSet<>();
private Robot robot;
public void cleanRoom(Robot robot) {
this.robot = robot;
dfs(0, 0, 0);
}
private void dfs(int i, int j, int d) {
robot.clean();
vis.add(List.of(i, j));
for (int k = 0; k < 4; ++k) {
int nd = (d + k) % 4;
int x = i + dirs[nd], y = j + dirs[nd + 1];
if (!vis.contains(List.of(x, y)) && robot.move()) {
dfs(x, y, nd);
robot.turnRight();
robot.turnRight();
robot.move();
robot.turnRight();
robot.turnRight();
}
robot.turnRight();
}
}
}/**
* // This is the robot's control interface.
* // You should not implement it, or speculate about its implementation
* class Robot {
* public:
* // Returns true if the cell in front is open and robot moves into the cell.
* // Returns false if the cell in front is blocked and robot stays in the current cell.
* bool move();
*
* // Robot will stay in the same cell after calling turnLeft/turnRight.
* // Each turn will be 90 degrees.
* void turnLeft();
* void turnRight();
*
* // Clean the current cell.
* void clean();
* };
*/
class Solution {
public:
void cleanRoom(Robot& robot) {
int dirs[5] = {-1, 0, 1, 0, -1};
set<pair<int, int>> vis;
function<void(int, int, int)> dfs = [&](int i, int j, int d) {
robot.clean();
vis.insert({i, j});
for (int k = 0; k < 4; ++k) {
int nd = (d + k) % 4;
int x = i + dirs[nd], y = j + dirs[nd + 1];
if (!vis.count({x, y}) && robot.move()) {
dfs(x, y, nd);
robot.turnRight();
robot.turnRight();
robot.move();
robot.turnRight();
robot.turnRight();
}
robot.turnRight();
}
};
dfs(0, 0, 0);
}
};/**
* // This is the robot's control interface.
* // You should not implement it, or speculate about its implementation
* type Robot struct {
* }
*
* // Returns true if the cell in front is open and robot moves into the cell.
* // Returns false if the cell in front is blocked and robot stays in the current cell.
* func (robot *Robot) Move() bool {}
*
* // Robot will stay in the same cell after calling TurnLeft/TurnRight.
* // Each turn will be 90 degrees.
* func (robot *Robot) TurnLeft() {}
* func (robot *Robot) TurnRight() {}
*
* // Clean the current cell.
* func (robot *Robot) Clean() {}
*/
func cleanRoom(robot *Robot) {
vis := map[[2]int]bool{}
dirs := [5]int{-1, 0, 1, 0, -1}
var dfs func(int, int, int)
dfs = func(i, j, d int) {
vis[[2]int{i, j}] = true
robot.Clean()
for k := 0; k < 4; k++ {
nd := (d + k) % 4
x, y := i+dirs[nd], j+dirs[nd+1]
if !vis[[2]int{x, y}] && robot.Move() {
dfs(x, y, nd)
robot.TurnRight()
robot.TurnRight()
robot.Move()
robot.TurnRight()
robot.TurnRight()
}
robot.TurnRight()
}
}
dfs(0, 0, 0)
}/**
* class Robot {
* // Returns true if the cell in front is open and robot moves into the cell.
* // Returns false if the cell in front is blocked and robot stays in the current cell.
* move(): boolean {}
*
* // Robot will stay in the same cell after calling turnLeft/turnRight.
* // Each turn will be 90 degrees.
* turnRight() {}
*
* // Robot will stay in the same cell after calling turnLeft/turnRight.
* // Each turn will be 90 degrees.
* turnLeft() {}
*
* // Clean the current cell.
* clean(): {}
* }
*/
function cleanRoom(robot: Robot) {
const dirs = [-1, 0, 1, 0, -1];
const vis = new Set<string>();
const dfs = (i: number, j: number, d: number) => {
vis.add(`${i}-${j}`);
robot.clean();
for (let k = 0; k < 4; ++k) {
const nd = (d + k) % 4;
const [x, y] = [i + dirs[nd], j + dirs[nd + 1]];
if (!vis.has(`${x}-${y}`) && robot.move()) {
dfs(x, y, nd);
robot.turnRight();
robot.turnRight();
robot.move();
robot.turnRight();
robot.turnRight();
}
robot.turnRight();
}
};
dfs(0, 0, 0);
}