February 15, 2022: sweeping robot. There is a floor sweeping robot in the room (represented by a grid). Each grid in the grid has two possibilities: empty and obstacles. The sweeping robot provides fo

2022-02-15： Sweeping robot .
room （ Use a grid to represent ） There is a sweeping robot in the .
Each grid in the grid has two possibilities: empty and obstacle .
The sweeping robot provides 4 individual API, Can move forward , Turn left or right . Every turn 90 degree .
When the sweeping robot tries to enter the obstacle grid , Its collision sensor will detect obstacles , Keep it where it is .
Please use the provided 4 individual API Write an algorithm to let the robot clean the whole room .
interface Robot {
// If the next box is empty , Then return to true, And move to this square
// If the next box is an obstacle , Then return to false, And stay where you are
boolean move();

// Calling turnLeft/turnRight After that, the robot will stay in its original position
// Every turn 90 degree
void turnLeft();
void turnRight();

// Clear the square
void clean();
}
Input :
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

analysis :
For room grille 0 or 1 fill .0 It means an obstacle ,1 Means that it can be passed .
Robot from row=1,col=3 Starting from the initial position of . Below the line in the upper left corner , Three columns to the right .

Be careful :
Input is only used to initialize the position of the room and robot . You need “ Blind solution ” This problem .
In other words , You have to know nothing about the room and the location of the robot , Use only 4 A given API solve the problem .
The initial position of the sweeping robot must be an open space .
The initial direction of the sweeping robot is upward .
All accessible grids are connected , That is, all are marked as 1 All grid robots can reach .
It can be assumed that the grid is surrounded by walls .
Power button 489.

answer 2022-02-15：

map Record the road .
0 On ,1 Right ,2 Next ,3 Left .
recursive .

The code to use golang To write . The code is as follows ：

package main

import "strconv"

func main() {
    

}

//  Do not submit the contents of this interface 
type Robot interface {
    
    move() bool

    turnLeft()

    turnRight()

    clean()
}

//  Submit the following 
func cleanRoom(robot Robot) {
    
    clean(robot, 0, 0, 0, make(map[string]struct{
    }))
}

var ds = [][]int{
    {
    -1, 0}, {
    0, 1}, {
    1, 0}, {
    0, -1}}

//  robot robot,
//  Where you are now (x,y), And I haven't been here before 
//  In what direction does the robot face d,0 1 2 3
// visited It records where the robot walked 
//  Function functions ： Don't repeat visited The location inside , Put the rest of the position , Clean it up ！
//  And going back ！
func clean(robot Robot, x, y, d int, visited map[string]struct{
    }) {
    
    robot.clean()
    visited[strconv.Itoa(x)+"_"+strconv.Itoa(y)] = struct{
    }{
    }
    for i := 0; i < 4; i++ {
    
        // d = 0 : 0 1 2 3
        // d = 1 : 1 2 3 0
        // d = 2 : 2 3 0 1
        // d = 3 : 3 0 1 2
        //  The next step ！
        nd := (i + d) % 4
        //  The direction of the next step is set ！ Where is the next step ？(nx, ny)
        nx := ds[nd][0] + x
        ny := ds[nd][1] + y
        _, ok := visited[strconv.Itoa(nx)+"_"+strconv.Itoa(ny)]
        if !ok && robot.move() {
    
            clean(robot, nx, ny, nd, visited)
        }
        robot.turnRight()
    }
    //  Responsible for going back ： Previous position , How to get to you ！ You're going back , And the direction is the same as before you , Should agree ！
    robot.turnRight()
    robot.turnRight()
    robot.move()
    robot.turnRight()
    robot.turnRight()
}

---

Zuo Shen java Code