​LeetCode刷题实战489:扫地机器人

共 2590字,需浏览 6分钟

 ·

2022-01-09 20:50

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !

今天和大家聊的问题叫做 扫地机器人,我们先来看题面:
https://leetcode-cn.com/problems/robot-room-cleaner/


示例                         


输入:
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
解析:
房间格栅用01填充。0表示障碍物,1表示可以通过。
机器人从row=1,col=3的初始位置出发。在左上角的一行以下,三列以右。


解题

http://www.javashuo.com/article/p-yvxgcwal-mq.html

给了咱们一个扫地机器人,给了4个 API 函数可供咱们调用,具体实现不用咱们操心,让咱们实现打扫房间 cleanRoom 函数。给的例子中有房间和起始位置的信息,可是代码中却没有,摆明是不想让咱们被分心。想一想也是,难道咱们在给扫地机器人编程时,还必需要知道用户的房间信息么?

固然不可以啦,题目中也说了让咱们盲目 Blindfolded 一些,因此就盲目的写吧。既然是扫地,那么确定要记录哪些位置已经扫过了,因此确定要记录位置信息,因为不知道全局位置,那么只能用相对位置信息了。初始时就是 (0, 0),而后上下左右加1减1便可。位置信息就放在一个 HashSet 中就能够了,同时为了方便,还能够将二维坐标编码成一个字符串。

咱们采用递归 DFS 来作,初始化位置为 (0, 0),而后建一个上下左右的方向数组,使用一个变量 dir 来从中取数。在递归函数中,咱们首先对起始位置调用 clean 函数,由于题目中说了起始位置是能到达的,便是为1的地方。而后就要把起始位置加入 visited。而后咱们循环四次,由于有四个方向,因为递归函数传进来的 dir 是上一次转到的方向,那么此时咱们 dir 加上i,为了防止越界,对4取余,就是咱们新的方向了,而后算出新的位置坐标 newX 和 newY。此时先要判断 visited 不含有这个新位置,即新位置没有访问过,还要调用 move 函数来肯定新位置是否能够到达,若这两个条件都知足的话,咱们就对新位置调用递归函数。注意递归函数调用完成后,咱们要回到调用以前的状态,由于这里的 robot 是带了引用号的,是全局通用的,因此要回到以前的状态。回到以前的状态很简单,由于这里的机器人的运做方式是先转到要前进的方向,才能前进。那么咱们后退的方法就是,旋转 180 度,前进一步,再转回到原来的方向。

同理,咱们在按顺序试上->右->下->左的时候,每次机器人要向右转一下,由于 move 函数只能探测前方是否能到达,因此咱们必须让机器人转到正确的方向,才能正确的调用 move 函数。若是用过扫地机器人的童鞋应该会有影响,当前方有障碍物的时候,机器人圆盘会先转个方向,而后再继续前进,这里要实现的机制也是相似的,参见代码以下:

class Solution {
public:
    vector<vector<int>> dirs{{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
    void cleanRoom(Robot& robot) {
        unordered_set<string> visited;
        helper(robot, 0, 0, 0, visited);
    }
    void helper(Robot& robot, int x, int y, int dir, unordered_set<string>& visited) {
        robot.clean();
        visited.insert(to_string(x) + "-" + to_string(y));
        for (int i = 0; i < 4; ++i) {
            int cur = (i + dir) % 4, newX = x + dirs[cur][0], newY = y + dirs[cur][1];
            if (!visited.count(to_string(newX) + "-" + to_string(newY)) && robot.move()) {
                helper(robot, newX, newY, cur, visited);
                robot.turnRight();
                robot.turnRight();
                robot.move();
                robot.turnLeft();
                robot.turnLeft();
            }
            robot.turnRight();
        }
    }
};


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。

上期推文:

LeetCode1-480题汇总,希望对你有点帮助!

LeetCode刷题实战481:神奇字符串

LeetCode刷题实战482:密钥格式化

LeetCode刷题实战483:最小好进制

LeetCode刷题实战484:寻找排列

LeetCode刷题实战485:最大连续 1 的个数

LeetCode刷题实战486:预测赢家

LeetCode刷题实战487:最大连续1的个数 II

LeetCode刷题实战488:祖玛游戏


浏览 17
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报