Find Area of Room by Robot

Find Area of Room with Robot

Facebook Interview Google Interview Graph DFS

There is a robot in a room. The initial location of the robot is unknown. The shape or area of the room is unknown.
You have a remote that could walk the robot into any of the four directions - up, left, down or right. Here is the move method:

boolean move(int direction)  

direction: {0: up, 1; left, 2: right, 3: down}
If the robot hits the wall, the method returns false.
Otherwise returns true and the robot moves on to the direction given.

Find out the area of the room.

e.g.
X
XXXX
XX
'X' marks the floor plan of the room.

A room as above has an area of 10.

Solution

This is a graph traversal problem. Either BFS or DFS could work to scan through the room.
The trick is when initial location is unknown, mark it as (0, 0) in a 2D grid.
When robot goes left: (x - 1, y)
When robot goes right: (x + 1, y)
When robot goes up: (x , y + 1)
When robot goes down: (x , y - 1)

How to store the visited locations with this setup?
There are two ways:

I. Have a class Point {int x; int y;} and a HashSet<Point>
Rewrite the equals function for Point into whenever point1.x == point2.x && point1.y == point2.y return true for point1.equals(point2).

II. Have a HashMap<Integer, HashSe<Integer>>;

    {
        x1 : {y11, y12, y13}, 
        x2 : {y22},
        x3 : {y31, y32}
    }

A map like above marks the visited nodes (x1, y11), (x1, y12), (x1, y13), (x2, y22), (x3, y31) and (x3, y32).

Both methods support finding a visited node in constant time.

Implementation

With the robot setup in the question, it is best to go with DFS since it’s easier to move the robot around with DFS. Remember to move the robot back to the node which it comes from after each round of searching.

public class AreaOfRoom {
    Robot robot;

    //x, y is the current location of the robot
    //from is the last step taken
    //map<x, set<y>> marks the places visited
    public int getArea(int x, int y, int from, Map<Integer, Set<Integer>> room) {
        if(room.containsKey(x) && room.get(x).contains(y)) { //if this place was visited
            robot.move(moveBack(from));        //turn robot back
            return 0;              //add 0 to total area
        }
        //mark current place visited
        if(!room.containsKey(x)) room.put(x, new HashSet<>());
        room.get(x).add(y);
        int area = 1;
        if(from != 0 && robot.move(moveBack(0))) {
            area += getArea(x, y - 1, 0, room);
        }
        if(from != 1 && robot.move(moveBack(1))) {
            area += getArea(x + 1, y, 1, room);
        }
        if(from != 2 && robot.move(moveBack(2))) {
            area += getArea(x, y + 1, 2, room);
        }
        if(from != 3 && robot.move(moveBack(3))) {
            area += getArea(x - 1, y, 2, room);
        }
        //having got the areas around the current location, walk robot back to where it was from
        robot.move(moveBack(from));
        return area;
    }

    private int moveBack(int from) {
        if(from == 0) return 2;
        if(from == 1) return 3;
        if(from == 2) return 0;
        return 1;
    }
}