Buggy Robot#8202
You need to program a robot to move through a two-dimensional maze and find the exit.
The maze is represented as a grid with rows and columns. Some cells contain obstacles that the robot cannot enter; the other cells are empty and the robot can move through them freely. Exactly one empty cell is marked as the exit. The robot leaves the maze immediately upon reaching this exit cell.
You can program the robot by sending it a command string consisting of the characters L, U, R, D, corresponding to the directions left, up, right, and down, respectively. The robot executes the commands in order, each moving it to the adjacent cell in the specified direction. If the robot encounters an obstacle or the edge of the grid, it ignores the command but continues with the remaining commands. The robot ignores any further commands after reaching the exit cell.
Your friend has provided a draft of the command string, but it may not guide the robot to the exit. You wish to modify this command string so that the robot will reach the exit cell. In one second, you may delete any character or insert any character at any position. Find the minimum time required to correct the command string so that the robot reaches the exit.
You do not care how long it takes the robot to reach the exit, only the time required to fix the command string.
The first line contains two integers and (1 \le n, m \le 50).
Each of the next lines contains characters describing the grid. Empty cells are denoted by `.'. The robot's initial position is marked by R, obstacles by #, and the exit by E.
The next and final line contains your friend's command string, consisting of between and characters, inclusive.
It is guaranteed that the grid contains exactly one R and one E, and that there is always a path from R to E.
Print a single integer—the minimum time required to correct the program.
Example 1
Example 2