Solution to "Robot Room Cleaner" on Leetcode

RobotRoomCleaner.java

/**
 * // This is the robot's control interface.
 * // You should not implement it, or speculate about its implementation
 * interface Robot {
 *     // 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.
 *     public boolean move();
 *
 *     // Robot will stay in the same cell after calling turnLeft/turnRight.
 *     // Each turn will be 90 degrees.
 *     public void turnLeft();
 *     public void turnRight();
 *
 *     // Clean the current cell.
 *     public void clean();
 * }
 */

class Solution {
    /**
     * Approach:
     * - Tree the room as a graph. Although we don't know the initial position the robot is on, we can model the room
     * as a graph of cells (see Cell class).
     * - When we visit each cell, we perform a dfs on all it's neighbors and continue that dfs until we have cleaned
     * the whole room
     * - How do we know cells we've visited? Our cell class provides int x and int y for positioning in the room
     * To go left from Cell: x - 1, y
     * To go right from a Cell: x + 1, y
     * To go upward from a Cell: x, y + 1
     * To go downward from a Cell: x, y - 1
     * - Every time we visit a cell, we store its positions in a Set, so that we don't visit it more than once
     */
    public void cleanRoom(Robot robot) {
        Set<String> visited = new HashSet<>();
        cleanRoom(robot, new Cell(0, 0), visited);
    }

    // This can be replaced with cleanRoom(Robot robot, int x, int y, Set<String> visited)
    // This removes the need for the Cell object
    private void cleanRoom(Robot robot, Cell cell, Set<String> visited) {
        String key = cell.x + "." + cell.y;
        //System.out.println(visited);
        if (visited.contains(key)) {
            return;
        }

        visited.add(key);
        robot.clean();
        //Go up
        cleanUpward(robot, cell, visited);
        //Go down
        cleanDownward(robot, cell, visited);
        //Go left
        cleanLeftward(robot, cell, visited);
        //Go right
        cleanRightward(robot, cell, visited);

    }

    private void cleanUpward(Robot robot, Cell cell, Set<String> visited) {
        if (!robot.move()) {
            return;
        }

        Cell upCell = new Cell(cell.x, cell.y - 1);
        cleanRoom(robot, upCell, visited);

        //Return to original upward positon
        robot.turnRight();
        robot.turnRight();
        robot.move();
        robot.turnLeft();
        robot.turnLeft();
    }

    private void cleanDownward(Robot robot, Cell cell, Set<String> visited) {
        robot.turnRight();
        robot.turnRight();
        if (!robot.move()) {
            robot.turnLeft();
            robot.turnLeft();
            return;
        }

        robot.turnLeft();
        robot.turnLeft();
        Cell downCell = new Cell(cell.x, cell.y + 1);
        cleanRoom(robot, downCell, visited);

        robot.move();
    }

    private void cleanLeftward(Robot robot, Cell cell, Set<String> visited) {
        robot.turnLeft();
        if (!robot.move()) {
            robot.turnRight();
            return;
        }

        robot.turnRight();
        Cell leftCell = new Cell(cell.x - 1, cell.y);
        cleanRoom(robot, leftCell, visited);

        robot.turnRight();
        robot.move();
        robot.turnLeft();
    }

    private void cleanRightward(Robot robot, Cell cell, Set<String> visited) {
        robot.turnRight();
        if (!robot.move()) {
            robot.turnLeft();
            return;
        }

        robot.turnLeft();
        Cell rightCell = new Cell(cell.x + 1, cell.y);
        cleanRoom(robot, rightCell, visited);

        robot.turnLeft();
        robot.move();
        robot.turnRight();
    }
}

class Cell {
    int x;
    int y;

    Cell(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

RobotRoomCleanerII.java

public class Solution2 {
    /**
     * Approach:
     * - Treat the room as a graph. Although we don't know the initial position the robot is on, we can model the room
     * as a graph of cells (see Cell class).
     * - When we visit each cell, we perform a dfs on all it's neighbors and continue that dfs until we have cleaned
     * the whole room
     * - How do we know cells we've visited? Our cell class provides int x and int y for positioning in the room
     * To go left from Cell: x - 1, y
     * To go right from a Cell: x + 1, y
     * To go upward from a Cell: x, y + 1
     * To go downward from a Cell: x, y - 1
     * - Every time we visit a cell, we store its positions in a Set, so that we don't visit it more than once
     */

    Robot robot;
    Set<Cell> visited = new HashSet<>();

    public void cleanRoom(Robot robotRef) {
        robot = robotRef;
        cleanCell(new Cell(0, 0));
    }

    // This can be replaced with cleanRoom(Robot robot, int x, int y, Set<String> visited)
    // This removes the need for the Cell object
    private void cleanCell(Cell cell) {
        if (visited.contains(cell)) {
            return;
        }

        visited.add(cell);
        robot.clean();
        cleanUpward(cell);
        cleanDownward(cell);
        cleanLeftward(cell);
        cleanRightward(cell);
    }

    private void cleanUpward(Cell cell) {
        boolean canMove = robot.move();
        if (!canMove) {
            return;
        }

        Cell upCell = new Cell(cell.x, cell.y - 1);
        cleanCell(upCell);

        //Return to original upward position
        turnDown();
        robot.move();
        turnUp();
    }

    private void cleanDownward(Cell cell) {
        turnDown();
        boolean canMove = robot.move();
        if (!canMove) {
            turnUp();
            return;
        }

        turnUp();
        Cell downCell = new Cell(cell.x, cell.y + 1);
        cleanCell(downCell);

        //Return to original upward position
        robot.move();
    }

    private void cleanLeftward(Cell cell) {

        robot.turnLeft();
        boolean canMove = robot.move();
        if (!canMove) {
            robot.turnRight();
            return;
        }

        robot.turnRight();
        Cell leftCell = new Cell(cell.x - 1, cell.y);
        cleanCell(leftCell);

        //Return to original upward position
        robot.turnRight();
        robot.move();
        robot.turnLeft();
    }

    private void cleanRightward(Cell cell) {
        robot.turnRight();
        boolean canMove = robot.move();
        if (!canMove) {
            robot.turnLeft();
            return;
        }

        robot.turnLeft();
        Cell rightCell = new Cell(cell.x + 1, cell.y);
        cleanCell(rightCell);

        //Return to original upward position
        robot.turnLeft();
        robot.move();
        robot.turnRight();
    }

    private void turnDown() {
        robot.turnRight();
        robot.turnRight();
    }

    private void turnUp() {
        robot.turnLeft();
        robot.turnLeft();
    }
}

class Cell {
    int x;
    int y;

    Cell(int x, int y) {
        this.x = x;
        this.y = y;
    }

    @Override
    public boolean equals(Object o) {
        if (o == this) return true;
        if (!(o instanceof Cell)) {
            return false;
        }

        Cell cell = (Cell) o;
        return cell.x == x && cell.y == y;
    }

    @Override
    public int hashCode() {
        String key = x + "." + y;
        return key.hashCode();
    }
}