Robot Room Cleaner
给一个robot的api, 问如何清洁一个room.
这题是设计题, 主要还是考虑怎么设计robot的走位, 肯定是dfs没错, 因为room的大小不知道, 所以要按照一定顺序走, 因为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 |
/** * // 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: int dirs[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};// up(default), right, down, left unordered_map<int, unordered_map<int, bool>> v; void cleanRoom(Robot& robot) { dfs(0,0,0,robot); } void dfs(int x, int y, int cur, Robot& robot){ if(v[x][y]) // if visited return; robot.clean(); v[x][y] = 1; for(int i = 0; i < 4; i++){ if(robot.move()){ int dd = (i + cur) % 4; dfs(x + dirs[dd][0], y + dirs[dd][1], dd, robot); robot.turnLeft(); robot.turnLeft(); // 180 degree robot.move(); robot.turnRight(); robot.turnRight(); } robot.turnRight(); } } }; |