Interview Question
- 0of 0 votes
AnswersYou are given a grid with R rows and C columns. You are also given a robot which is very small and can be placed on the grid - to walk around in the grid. You will place the robot at some starting cell of your choosing. You will give the robot an initial direction. Then, when you start the robot, it will walk in the given direction till it gets out of the grid or encounters a "turn" cell in the grid.
- lodhi November 30, 2015 in United States
Each cell in the grid is either empty (depicted by '.') or a turn cell (depicted by 'r' or 'l'). When the robot encounters a turn cell with 'r', it will turn right on that cell. Note that this turn will be relative to the direction in which the robot is moving. Similarly, when the robot encounters a turn cell with 'l', it will turn left on that cell. The examples and explanations clarify this.
The robot will eventually leave the grid or enter a loop. You wish to choose a start point and direction for the robot such that it visits the maximum number of unique cells. Note that the start point you select must be an empty cell.
Print the maximum number of unique cells the robot will visit when you choose such a starting point.
Input
The first line of input contains a number T, the number of test cases. Then follows the description of T test cases. The first line of each test case contains two integers R and C. On the next R lines are exactly C characters each. Each character is either '.', 'r' or 'l'.
Output
For each test case, output a single number on a line by itself. This number should be the maximum number of unique cells the robot can visit if you place it optimally.
Constraints
1 ≤ T ≤ 20
1 ≤ R ≤ 20
1 ≤ C ≤ 20
Attention
The constraints are designed such that O(R*R*C*C) solutions will pass.
Sample Input
3
3 5
.....
...r.
...r.
2 2
..
..
1 5
.r...
Sample Output
8
2
4
Explanation
We will assume that the rows are labeled from 1 to R from top to bottom and columns are labeled from 1 to C from left to right.
In the first test case the optimal choice is to keep the robot at 2,1 facing east. The robot will move as 2,1 - 2,2 - 2,3 - 2,4 and then turn right, facing south. The robot will then move as 2,4 - 3,4 and then turn right, facing west. The robot will then move as 3,4 - 3,3 - 3,2 - 3,1 and then leave the grid. The robot touched 8 unique cells.
In the second test case you cannot optimise robot placement. No matter what you do, you can only touch 2 different cells.
In the third test case the optimal choice is to place the robot on 1,5 facing west.| Report Duplicate | Flag | PURGE