Untitled

mail@pastecode.io avatar
unknown
plain_text
20 days ago
1.7 kB
0
Indexable
Never
/**
 * // 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 row[4] = {-1, 0, 1, 0};
    int col[4] = {0, 1, 0, -1};
    set<pair<int, int>> visited;

public:
    void goBack(Robot &robot) {
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnRight();
        robot.turnRight();
    }

    void backtrack(Robot &robot, int currRow, int currCol, int facingTowards) {
        visited.insert({currRow, currCol});
        robot.clean();
        for (int i = 0; i < 4; i++) { // observe that it has rotated 4 times therefore in the end
                    // it will face towards the direction it was facing earlier
            int nowFaceTowards = (facingTowards + i) % 4;
            int newRow = currRow + row[nowFaceTowards];
            int newCol = currCol + col[nowFaceTowards];
            if (!visited.count({newRow, newCol}) && robot.move()) {
                backtrack(robot, newRow, newCol, nowFaceTowards);
                this->goBack(robot);
            }
            robot.turnRight();
        }
    }

    void cleanRoom(Robot& robot) {
        backtrack(robot, 0, 0, 0);
    }
};
Leave a Comment