Problem:
The product robot room cleaner works as follows: | |
|
The robot can move forward, turn 90 degrees left, turn 90 degrees right.These movement allows it to move around. The robot also has a sensor to detect obstacles. Before the robot moves forward, the sensor will detect if an obstacle is located on the position it will move to, if yes, the robot cancels the move, then does a left or right turn then attempts to move forward.
Given a robot cleaner and a room floor that is divided into cells.
Each cell can be empty or blocked.
Design an algorithm to clean the entire floor using only the 4 given APIs shown below.
interface Robot {
// returns true if next cell is open and robot moves into the cell.
// returns false if next cell is blocked and robot stays on the current cell.
boolean forward();
// 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();
}
For Example:
Given room cells
room = [
[1,0,1,1,1,0,1,1],
[1,0,0,0,1,0,1,1],
[1,0,1,1,1,0,1,0],
[0,0,0,0,0,0,0,0],
[1,1,1,1,1,1,1,0]
],
All cells in the room are marked by either 0 or 1. All the cells outside of the matrix are blocked.
1 means the cell is blocked, while 0 means the cell is open. All open cells are connected.
The robot is put on a random open position, for example room[0][1] with initial direction of facing up.
Solution:
This is a standard dfs maze traversal problem. The news about this problem is the robot need to take corresponding actions during the dfs traversal, therefore we need to have a deep understanding of dfs process.
import java.util.*;
//import you.hardware.provider.package.*;
//invoke the program with command: java -cp .:HardwareVendorProvided.jar Solution
class Solution {
private Set<Point> visited = new HashSet<>();
/*replace this with a large enough all 0 2-d array when used with hardware
the (room size / distance of robot forward moving) will decide the size of the 2-d array. It is large enough so that you can put the robot at center and there are cells in all 4 directions to cover the whole room area. */
private static int[][] room = {
{1,0,1,1,1,0,1,1},
{1,0,0,0,0,0,1,1},
{1,0,1,1,1,0,1,0},
{0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,0}
};
private static int N = room.length;
private static int M = room[0].length;
//private static Robot robot = RobotFactory.makeRobot();
public static void main(String[] args) {
int x = 0;
int y = 1;
Solution s = new Solution();
s.dfs(x, y);
printRoom();
}
private void dfs(int row, int col) {
visited.add(new Point(row, col));
//robot.clean();
room[row][col] = 2;
int[] rowMask = new int[]{-1, 0, 1, 0};
int[] colMask = new int[]{0, 1, 0, -1};
for(int i = 0; i < rowMask.length; i++) {
int nextRow = row + rowMask[i];
int nextCol = col + colMask[i];
if(canMove(nextRow, nextCol)) {
dfs(nextRow, nextCol);
} else {
//robot.turnRight();
}
}
//moveBack();
}
private void moveBack() {
//robot.turnRight();
//robot.turnRight();
//robot.forward();
//robot.turnLeft();
}
private boolean canMove(int row, int col) {
if(visited.contains(new Point(row, col)))
return false;
//simulate sensor
//return robot.forward();
if(row < 0 || row >= N || col < 0 || col >= M)
return false;
return room[row][col] == 0;
}
private static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public boolean equals(Object o) {
if(o == null) return false;
if(!(o instanceof Point)) return false;
Point other = (Point)o;
return this.x == other.x && this.y == other.y;
}
public int hashCode() {
return 31*x + y;
}
}
private static void printRoom() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
System.out.print(room[i][j] + " ");
}
System.out.println();
}
}
}
//import you.hardware.provider.package.*;
//invoke the program with command: java -cp .:HardwareVendorProvided.jar Solution
class Solution {
private Set<Point> visited = new HashSet<>();
/*replace this with a large enough all 0 2-d array when used with hardware
the (room size / distance of robot forward moving) will decide the size of the 2-d array. It is large enough so that you can put the robot at center and there are cells in all 4 directions to cover the whole room area. */
private static int[][] room = {
{1,0,1,1,1,0,1,1},
{1,0,0,0,0,0,1,1},
{1,0,1,1,1,0,1,0},
{0,0,0,0,0,0,0,0},
{1,1,1,1,1,1,1,0}
};
private static int N = room.length;
private static int M = room[0].length;
//private static Robot robot = RobotFactory.makeRobot();
public static void main(String[] args) {
int x = 0;
int y = 1;
Solution s = new Solution();
s.dfs(x, y);
printRoom();
}
private void dfs(int row, int col) {
visited.add(new Point(row, col));
//robot.clean();
room[row][col] = 2;
int[] rowMask = new int[]{-1, 0, 1, 0};
int[] colMask = new int[]{0, 1, 0, -1};
for(int i = 0; i < rowMask.length; i++) {
int nextRow = row + rowMask[i];
int nextCol = col + colMask[i];
if(canMove(nextRow, nextCol)) {
dfs(nextRow, nextCol);
} else {
//robot.turnRight();
}
}
//moveBack();
}
private void moveBack() {
//robot.turnRight();
//robot.turnRight();
//robot.forward();
//robot.turnLeft();
}
private boolean canMove(int row, int col) {
if(visited.contains(new Point(row, col)))
return false;
//simulate sensor
//return robot.forward();
if(row < 0 || row >= N || col < 0 || col >= M)
return false;
return room[row][col] == 0;
}
private static class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
public boolean equals(Object o) {
if(o == null) return false;
if(!(o instanceof Point)) return false;
Point other = (Point)o;
return this.x == other.x && this.y == other.y;
}
public int hashCode() {
return 31*x + y;
}
}
private static void printRoom() {
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
System.out.print(room[i][j] + " ");
}
System.out.println();
}
}
}
Time complexity is O(4^N) where N is the number of open cells. At each open cell, there are 4 directions to choose, total number of choices are 4^N. The space complexity is O(N), it is the max size of the caller stack.
