首页 > 其他 > 详细

LeetCode 489. Robot Room Cleaner

时间:2019-09-05 09:39:20      阅读:59      评论:0      收藏:0      [点我收藏+]

dfs的问题,第一眼看上去不难,但是由于地图和位置信息都是不可知的,这导致 dfs 的时候坐标无从下手,同样判断是否访问过的 visited 也不好处理 。

本题的关键点在于,如何构建构建坐标系。令当前坐标为坐标原点,记录当前的方向,这样我们就能知道我们每次 move 以后的正确坐标了。然后就是标准dfs,有一点要注意的是,每次回溯的时候机器人要归位。

/**
 * // 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 {
public:
    vector<vector<int>> dirs={{-1,0},{0,1},{1,0},{0,-1}}; // up right down left
    unordered_map<int,unordered_map<int,bool>> visited; // visited[x][y]
    
    void cleanRoom(Robot& robot) {
        dfs(robot,0,0,0);
    }
    
    void dfs(Robot &robot, int i, int j, int dir){
        if (visited[i][j]) return;
        //cout << x << ‘ ‘ << y << endl;
        robot.clean(); visited[i][j]=true;
        
        for (int k=0;k<4;++k){
            if (robot.move()){
                dfs(robot,i+dirs[dir][0],j+dirs[dir][1],dir);
                robot.turnRight();
                robot.turnRight();
                robot.move();
                robot.turnRight();
                robot.turnRight();
            }
            robot.turnRight();
            dir = (dir+1)%4;
        }
    }
};

 

LeetCode 489. Robot Room Cleaner

原文:https://www.cnblogs.com/hankunyan/p/11462805.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!