本文共 2516 字，大约阅读时间需要 8 分钟。

1. 题目

房间（用格栅表示）中有一个扫地机器人。

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

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

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

interface Robot {
     // 若下一个方格为空，则返回true，并移动至该方格  // 若下一个方格为障碍物，则返回false，并停留在原地  boolean move();  // 在调用turnLeft/turnRight后机器人会停留在原位置  // 每次转弯90度  void turnLeft();  void turnRight();  // 清理所在方格  void clean();}

示例:输入: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的初始位置出发。在左上角的一行以下，三列以右。注意:输入只用于初始化房间和机器人的位置。你需要“盲解”这个问题。换而言之，你必须在对房间和机器人位置一无所知的情况下，只使用4个给出的API解决问题。 扫地机器人的初始位置一定是空地。扫地机器人的初始方向向上。所有可抵达的格子都是相连的，亦即所有标记为1的格子机器人都可以抵达。可以假定格栅的四周都被墙包围。

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/robot-room-cleaner

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

/** * // 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 {
       vector
   
    
     > dir = {
   {
   -1,0},{
   0,1},{
   1,0},{
   0,-1}};    unordered_set
     
       visited;public:    void cleanRoom(Robot& robot) {
           visited.insert("0-0");//坐标访问过        dfs(robot, 0, 0, 0);    }    void dfs(Robot& robot, int x, int y, int d)    {
           robot.clean();        int nx, ny, nd;        string pos;        for(int k = 1; k <= 4; ++k)        {
                  robot.turnRight();//换方向                  nd = (d+k)%4;            nx = x + dir[nd][0];            ny = y + dir[nd][1];            pos = to_string(nx)+"-"+to_string(ny);            if(visited.count(pos))//下一个位置访问过吗                continue;            if(robot.move())//没访问过，可以移动的话            {
                   visited.insert(pos);//访问了                dfs(robot, nx, ny, nd);//移动                robot.turnRight();//回溯，调转180度                robot.turnRight();                robot.move();//回退到原地                robot.turnRight();//再转180把方向调到之前走的状态                robot.turnRight();            }        }    }};
     
    
   

40 ms 9.9 MB

我的CSDN

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

转载地址：https://michael.blog.csdn.net/article/details/107581006 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！