## 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;
}
}
```

#### Get one-to-one training from Google Facebook engineers

##### Top-notch Professionals

Learn from Facebook and Google senior engineers interviewed 100+ candidates.

Most recent interview questions and system design topics gathered from aonecode alumnus.

One-to-one online classes. Get feedbacks from real interviewers.

##### Customized Private Class

Already a coding expert? - Advance straight to hard interview topics of your interest.

New to the ground? - Develop basic coding skills with your own designated mentor.

Days before interview? - Focus on most important problems in target company question bank.