算法leetcode

【搜索难题】力扣489-扫地机器人

字数统计: 1.1k字   |   阅读时长: 4分
,

摘要: 回溯法经典问题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 回溯法的思想、设计与分析 中，我们系统学习了回溯法的思想以及可以解决的问题。

在文章 回溯法三种常见的状态空间树：子集树、排列树、满m叉树 中，我们梳理了回溯法的三种常见的状态空间树，以及各自的适用场景。

在文章 n皇后-同一问题构造不同的状态空间树 中，我们在回溯法的框架下解决了 n 皇后问题，并且发现对于同一个问题，可以构造不同的状态空间树解决。

本文我们来看一个回溯法的应用，扫地机器人。

$1 题目

房间（用格栅表示）中有一个扫地机器人。格栅中的每一个格子有空和障碍物两种可能。

扫地机器人提供4个API，可以向前进，向左转或者向右转。每次转弯90度。

当扫地机器人试图进入障碍物格子时，它的碰撞传感器会探测出障碍物，使它停留在原地。

请利用提供的4个API编写让机器人清理整个房间的算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
interface Robot {
  // 若下一个方格为空，则返回true，并移动至该方格
  // 若下一个方格为障碍物，则返回false，并停留在原地
  boolean move();

  // 在调用turnLeft/turnRight后机器人会停留在原位置
  // 每次转弯90度
  void turnLeft();
  void turnRight();

  // 清理所在方格
  void clean();
}

注意:

1
2
3
4
5
输入只用于初始化房间和机器人的位置。你需要“盲解”这个问题。换而言之，你必须在对房间和机器人位置一无所知的情况下，只使用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

解析:
房间格栅用0或1填充。0表示障碍物，1表示可以通过。
机器人从row=1，col=3的初始位置出发。在左上角的一行以下，三列以右。

$2 题解

算法: 回溯

机器人在房间内 DFS，在当前位置，机器人要依次干下面几件事：

step1. 清理当前位置，也就是调用 clean()，标记当前点以清扫。

step2. 依次判断四个方向的相邻格子是否是障碍或者已经清扫过，

  • 如果不是障碍且没有清扫过，则前进到该位置继续 DFS，回溯后向右转。
  • 否则向左转。

step3. 四个方向搜索完后，回溯到上一次搜索，先调头，再前进。

在 DFS 过程中，带着当前点的坐标 (x, y)，起始点为 (0, 0)，用哈希表记录已经清扫过的点。带着方向，初始时是向上, 上左下右分别为 ori=0,1,2,3。

代码(C++)

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 Solution {
public:
    void cleanRoom(Robot& robot) {
        dfs(robot, 0, 0, 0);
    }

private:
    unordered_set<int> setting;
    const int p = 21101;
    const int MOD = 1e9 + 7;
    using ll = long long;
    int hash(int x, int y)
    {
        return ((ll)x * p + y) % MOD;
    }
    /*
     * ori:
     *  0: 上
     *  1: 左
     *  2: 下
     *  3: 右
     */
    int dx[4] = {-1, 0, 1, 0};
    int dy[4] = {0, -1, 0, 1};

    void dfs(Robot& robot, int x, int y, int ori)
    {
        robot.clean();
        setting.insert(hash(x, y));
        for(int d = 0; d < 4; ++d)
        {
            int nxt_x = x + dx[ori];
            int nxt_y = y + dy[ori];
            if(setting.count(hash(nxt_x, nxt_y)) == 0 && robot.move())
            {
                dfs(robot, nxt_x, nxt_y, ori);
                robot.turnRight();
            }
            else
                robot.turnLeft();
            ori = (ori + 1) % 4;
        }
        // 回溯阶段
        robot.turnLeft();
        robot.turnLeft();
        robot.move();
    }
};
Share