[Hard] 489. Robot Room Cleaner (Java)

https://leetcode.com/problems/robot-room-cleaner/description/

Robot Room Cleaner - LeetCode

문제가 신기해

---

※  Question Summary

▶ You are controlling  a robot that is located somewhere in a room

▶ The room is modeled as an m x n binary grid where 0 represents a wall and 1 represents an empty slot

▶ The robot starts at an unknown location where is in empty slot

▶ You can move the robot using the given API Robot

▶ The robot with the four given APIs can move forward, turn left, or turn right. Each turn is 90 degrees

▶ When the robot tries to move into a wall cell, its bumper sensor detects the obstacle, and it stays on the cell

▶ Design the algorithm to clean the entire room using the following APIs

interface Robot {
  // returns true if next cell is open and robot moves into the cell.
  // returns false if next cell is obstacle and robot stays on the current cell.
  boolean move();

  // Robot will stay on the same cell after calling turnLeft/turnRight.
  // Each turn will be 90 degrees.
  void turnLeft();
  void turnRight();

  // Clean the current cell.
  void clean();
}

---

◈ Constraints

• m == room.length
• n == room[i].length
• 1 <= m <= 100
• 1 <= n <= 200
• room[i][j] is either 0 or 1.
• 0 <= row < m
• 0 <= col < n
• room[row][col] == 1
• All the empty cells can be visited from the starting position.

---

◈ Input - 1

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

◈ Output - 1

Robot cleaned all rooms.

◈ Input - 2

Input: room = [[1]], row = 0, col = 0

◈ Output - 2

Robot cleaned all rooms.

---

 ◎  HOW TO SOLVE IT

▶ Robot has to clean all rooms == robot has to go each cell only once

▶ Make the algorithms using backtracking to clean every cell

▶ The robot can only turn 90 degrees => set the searching direction to east => south => west => north

▶ Create the class 'Point' which has row and col

▶ Use the Hashset<Point> to check a cell has been visited during the backtracking

     ( can't use the array since can't define the size )

▶ Consider not only points but also robots after cleaning in your backtracking algorithms

---

/**
 * // 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 Point {
  int m_nRow;
  int m_nCol;

  Point(int nRow, int nCol){
    m_nRow = nRow;
    m_nCol = nCol;
  }

  @Override
	public boolean equals(Object o) {
		if (this == o) return true;
		if (o == null || getClass() != o.getClass()) return false;
		Point point = (Point) o;
		return m_nRow == point.m_nRow && m_nCol == point.m_nCol;
	}

   @Override
    public int hashCode() {
        return Objects.hash(m_nRow, m_nCol);
    }
}

class Solution {
    Set<Point> visitP = new HashSet<>();
    // east, south, west , north
    static int[] dr = {0,1,0, -1};
    static int[] dc = {1,0,-1, 0};
    public void cleanRoom(Robot robot) {
        clean(robot, 0, 0, 0);
    }

    public void clean(Robot robot, int nRow, int nCol, int nDirection) {
        // do the clean
        robot.clean();
        visitP.add(new Point(nRow, nCol));

        for(int k = 0; k < 4; k++) {
            int nSearchD = (nDirection + k);
            if(nSearchD > 3)
              nSearchD -= 4;
            int nSearchRow = nRow + dr[nSearchD];
            int nSearchCol = nCol + dc[nSearchD];

            if(!visitP.contains(new Point(nSearchRow, nSearchCol)) && robot.move()) {
                System.out.println(nSearchRow + " / " + nSearchCol);
                clean(robot, nSearchRow, nSearchCol, nSearchD);
                // the robot has to go back with the point
                robot.turnRight();
                robot.turnRight();
                robot.move();
                robot.turnRight();
                robot.turnRight();
            }

            robot.turnRight();
        }

    }
}

---

I HOPE YOUR DAY GOES WELL :)