Add solution #489

JoshCrozier · JoshCrozier · commit 6ca92e693c15 · 2025-06-17T23:53:38.000-05:00
diff --git a/README.md b/README.md
@@ -477,6 +477,7 @@
 486|[Predict the Winner](./solutions/0486-predict-the-winner.js)|Medium|
 487|[Max Consecutive Ones II](./solutions/0487-max-consecutive-ones-ii.js)|Medium|
 488|[Zuma Game](./solutions/0488-zuma-game.js)|Hard|
+489|[Robot Room Cleaner](./solutions/0489-robot-room-cleaner.js)|Hard|
 491|[Non-decreasing Subsequences](./solutions/0491-non-decreasing-subsequences.js)|Medium|
 492|[Construct the Rectangle](./solutions/0492-construct-the-rectangle.js)|Easy|
 493|[Reverse Pairs](./solutions/0493-reverse-pairs.js)|Hard|
diff --git a/solutions/0489-robot-room-cleaner.js b/solutions/0489-robot-room-cleaner.js
@@ -0,0 +1,78 @@
+/**
+ * 489. Robot Room Cleaner
+ * https://leetcode.com/problems/robot-room-cleaner/
+ * Difficulty: Hard
+ *
+ * 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 in the room that is guaranteed to be empty, and you do
+ * not have access to the grid, but you can move the robot using the given API Robot.
+ *
+ * You are tasked to use the robot to clean the entire room (i.e., clean every empty cell in the
+ * room). 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 current cell.
+ *
+ * Design an 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();
+ * }
+ *
+ * Note that the initial direction of the robot will be facing up. You can assume all four edges of
+ * the grid are all surrounded by a wall.
+ *
+ * Custom testing:
+ * The input is only given to initialize the room and the robot's position internally. You must
+ * solve this problem "blindfolded". In other words, you must control the robot using only the
+ * four mentioned APIs without knowing the room layout and the initial robot's position.
+ */
+
+/**
+ * @param {Robot} robot
+ * @return {void}
+ */
+var cleanRoom = function(robot) {
+  const visited = new Set();
+  const directions = [[-1, 0], [0, 1], [1, 0], [0, -1]];
+
+  backtrack(0, 0, 0);
+
+  function backtrack(row, col, dir) {
+    const key = `${row},${col}`;
+    if (visited.has(key)) return;
+
+    visited.add(key);
+    robot.clean();
+
+    for (let i = 0; i < 4; i++) {
+      const newDir = (dir + i) % 4;
+      const [dx, dy] = directions[newDir];
+      const newRow = row + dx;
+      const newCol = col + dy;
+
+      if (robot.move()) {
+        backtrack(newRow, newCol, newDir);
+        robot.turnRight();
+        robot.turnRight();
+        robot.move();
+        robot.turnLeft();
+        robot.turnLeft();
+      }
+      robot.turnRight();
+    }
+  }
+};
