/**
* // 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) {
}
};
/**
* // 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) {
visited := map[[2]int]bool{}
// 思维误区：考虑方向，顺时针=> 0:up 1:right 2: down, 3:left
dirs := [][]int{[]int{-1,0}, []int{0,1}, []int{1,0}, []int{0,-1}}
var dfs func(cur [2]int, direction int)
dfs = func(cur [2]int, direction int){
visited[cur] = true
robot.Clean()
// 思维误区：考虑方向，顺时针: 0: 'up', 1: 'right', 2: 'down', 3: 'left'
for i := range dirs{
next_dir := (direction+i) % 4
next := [2]int{cur[0]+dirs[next_dir][0], cur[1]+dirs[next_dir][1]}
if !visited[next] && robot.Move(){
dfs(next, next_dir)
// 此处递归回来后，robot 要回到原位置 并恢复朝向
robot.TurnLeft()
robot.TurnLeft()
robot.Move()
robot.TurnLeft()
robot.TurnLeft()
}
// turn the robot following chosen direction : clockwise
// 所以前提要求 robot 方向要恢复
robot.TurnRight()
}
}
dfs([2]int{0,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 final int[][] ds = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
public void cleanRoom(Robot robot) {
dfs(robot, 0, 0, 0, new HashSet<String>()); // 把机器人的初始坐标视为原点，初始方向朝上
}
private void dfs(Robot robot, int x, int y, int d, Set<String> visited) {
// 机器人先打扫完当前位置
visited.add(x + "," + y);
robot.clean();
// 然后尝试往四个方向走
for(int i = 0; i < 4; i++){
int nd = (d + i) % 4;
int nextX = x + ds[nd][0], nextY = y + ds[nd][1];
if(!visited.contains(nextX + "," + nextY) && robot.move()){
// 如果下一个位置没走过且不是障碍，就前往打扫
dfs(robot, nextX, nextY, nd, visited);
}
robot.turnRight();
}
// 机器人退回到上一个位置（它进来前的位置，且保持进来时的朝向），相当于回溯
robot.turnRight();
robot.turnRight();
robot.move();
robot.turnLeft();
robot.turnLeft();
}
}
/**
* // 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();
* };
*/
struct PairHash { // 自定义hash函数
size_t operator()(const pair<int, int>& key) const {
return hash<int>{}(key.first * 131) ^ hash<int>{}(key.second);
}
};
class Solution {
int dirs[4][2] = {-1, 0, 0, 1, 1, 0, 0, -1};
unordered_set<pair<int, int>, PairHash> vis; // 防止重复访问
public:
void cleanRoom(Robot& robot) {
dfs(robot, 0, 0, 0);
}
void dfs(Robot& robot, int x, int y, int di) {
vis.emplace(x, y); // 标记为已访问
robot.clean();
for (int i = 0; i < 4; ++i) {
int nd = (i + di) % 4, nx = x + dirs[nd][0], ny = y + dirs[nd][1];
if (vis.count(make_pair(nx, ny)) == 0 && robot.move()) {
dfs(robot, nx, ny, 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
* 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();
* }
*/
public class Pair<F, S> {
public F first;
public S second;
public Pair(F first, S second) {
this.first = first;
this.second = second;
}
@Override
public boolean equals(Object o) {
Pair<F, S> p = (Pair<F, S>) o;
return Objects.equals(p.first, first) && Objects.equals(p.second, second);
}
@Override
public int hashCode() {
return first.hashCode() ^ second.hashCode();
}
}
class Solution {
// going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
int[][] directions = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
Set<Pair<Integer, Integer>> visited = new HashSet();
Robot robot;
public void goBack() {
robot.turnRight();
robot.turnRight();
robot.move();
robot.turnRight();
robot.turnRight();
}
public void backtrack(int row, int col, int d) {
visited.add(new Pair(row, col));
robot.clean();
// going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
for (int i = 0; i < 4; ++i) {
int newD = (d + i) % 4;
int newRow = row + directions[newD][0];
int newCol = col + directions[newD][1];
if (!visited.contains(new Pair(newRow, newCol)) && robot.move()) {
backtrack(newRow, newCol, newD);
goBack();
}
// turn the robot following chosen direction : clockwise
robot.turnRight();
}
}
public void cleanRoom(Robot robot) {
this.robot = robot;
backtrack(0, 0, 0);
}
}
# """
# 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 go_back():
robot.turnRight()
robot.turnRight()
robot.move()
robot.turnRight()
robot.turnRight()
def backtrack(cell = (0, 0), d = 0):
visited.add(cell)
robot.clean()
# going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
for i in range(4):
new_d = (d + i) % 4
new_cell = (cell[0] + directions[new_d][0], \
cell[1] + directions[new_d][1])
if not new_cell in visited and robot.move():
backtrack(new_cell, new_d)
go_back()
# turn the robot following chosen direction : clockwise
robot.turnRight()
# going clockwise : 0: 'up', 1: 'right', 2: 'down', 3: 'left'
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]
visited = set()
backtrack()
