leetcode康复训练 Robot Room Cleaner 扫地机器人

发表于 更新于 分类于
未知房间矩阵，扫地机器人要求把所有能到达的格子都扫一遍（含测试代码）。

[LeetCode] 489. Robot Room Cleaner 扫地机器人

题目描述

Given a robot cleaner in a room modeled as a grid.

Each cell in the grid can be empty or blocked.

The robot cleaner with 4 given APIs can move forward, turn left or turn right. Each turn it made is 90 degrees.

When it tries to move into a blocked cell, its bumper sensor detects the obstacle and it stays on the current cell.

Design an algorithm to clean the entire room using only the 4 given APIs shown below.

1
2
3
4
5
6
7
8
9
10
11
12
13
interface Robot {
  // returns true if next cell is open and robot moves into the cell.
  // returns false if next cell is obstacle and robot stays on the current cell.
  boolean move();

  // Robot will stay on the same cell after calling turnLeft/turnRight.
  // Each turn will be 90 degrees.
  void turnLeft();
  void turnRight();

  // Clean the current cell.
  void clean();
}

Example:

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

Explanation:
All grids in the room are marked by either 0 or 1.
0 means the cell is blocked, while 1 means the cell is accessible.
The robot initially starts at the position of row=1, col=3.
From the top left corner, its position is one row below and three columns right.
Notes:

The input is only given to initialize the room and the robot’s position internally. You must solve this problem “blindfolded”. In other words, you must control the robot using only the mentioned 4 APIs, without knowing the room layout and the initial robot’s position.
The robot’s initial position will always be in an accessible cell.
The initial direction of the robot will be facing up.
All accessible cells are connected, which means the all cells marked as 1 will be accessible by the robot.
Assume all four edges of the grid are all surrounded by wall.

测试driver

Room

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import copy

class Room:

    def __init__(self, accessable=0, room_map=None):
        if not room_map:
            self._room_map = [[0, 0, 0, 0, 0, 1, 0, 0],
                              [0, 0, 0, 0, 0, 1, 0, 0],
                              [0, 1, 0, 0, 0, 0, 0, 0],
                              [1, 1, 1, 0, 1, 1, 1, 1],
                              [0, 0, 0, 0, 0, 0, 0, 0]]
        else:
            self._room_map = room_map
        self._cleaned_map = copy.deepcopy(self._room_map)
        self._x_length = len(self._room_map)
        self._y_length = len(self._room_map[0])
        self._accessable = accessable

    def canMoveTo(self, x, y):
        if x >= 0 and x < self._x_length and y >= 0 and y < self._y_length and self._room_map[x][y] == self._accessable:
            return True
        else:
            return False

    def clean(self, x, y):
        if self.canMoveTo(x, y) and self._cleaned_map[x][y] == self._accessable:
            self._cleaned_map[x][y] = 1

Robot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Robot:

    # direction can only be 0 1 2 3
    # top left corner of the room matrix is (0,0)
    # 0 means go down, 1 means go left, 2 means go up, 3 means go right
    def __init__(self, start_x: int = 0, start_y: int = 2, start_direction: int = 2, room: Room = Room()):
        self._room = room
        self._x = start_x
        self._y = start_y
        self._direction = start_direction
        print('room:\n', self._room._room_map)

    def move(self):
        if self._direction == 0:
            new_x = self._x + 1
            new_y = self._y
        elif self._direction == 1:
            new_x = self._x
            new_y = self._y - 1
        elif self._direction == 2:
            new_x = self._x - 1
            new_y = self._y
        elif self._direction == 3:
            new_x = self._x
            new_y = self._y + 1

        if(self._room.canMoveTo(new_x, new_y)):
            self._x = new_x
            self._y = new_y
            return True
        else:
            return False

    def turnLeft(self):
        # Use plus to avoid negative value
        # down -> turnLeft -> right
        # 0 -> 3, 1 -> 0, 2 -> 1, 3 -> 2
        self._direction = (self._direction + 3) % 4

    def turnRight(self):
        # 0 -> 1, 1 -> 2, 2 -> 3, 3 -> 0
        self._direction = (self._direction + 1) % 4

    def clean(self):
        self._room.clean(self._x, self._y)

    def printCleanMap(self):
        print(self._room._cleaned_map)

主函数

1
2
3
robot = Robot()
cleanAll(robot)
print(robot._room._cleaned_map)

Solution

思路是遍历每一格。

  • 进到这一格，首先clean清理地板
  • 把当前格的相对坐标加进visited
  • 开始转向往前走，注意回溯的时候，要先转180度，走一步回到当前格子，然后再转180度，保证回到最开始没有往前走的格子和方向。
  • 走四个方向
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
directions = [(-1, 0), (0, 1), (1, 0), (0, -1)]


def visit(robot, x, y, direction, visited):
    robot.clean()
    visited.add((x, y))
    for index in range(len(directions)):
        current_dir = (index+direction) % len(directions)
        new_x = x + directions[current_dir][0]
        new_y = y + directions[current_dir][1]
        if (new_x, new_y) not in visited and robot.move():
            visit(robot, new_x, new_y, current_dir, visited)
            robot.turnRight()
            robot.turnRight()
            robot.move()
            robot.turnLeft()
            robot.turnLeft()
        robot.turnRight()


def cleanAll(robot):
    visit(robot, 0, 0, 0, set())