You have built a new robot and placed it in a maze. The maze contains \(N\) rows and each row contains \(M\) cells. Each cell of the maze is either an empty cell or an obstacle. An empty cell is denoted by a (\(.\)) dot and an obstacle is denoted by a (\(\#\)) hash. The robot is operated by your computer with some keyboard commands. Currently, there are \(4\) character commands:
- \(L\): Moves the robot from the current cell to its left cell
- \(R\): Moves the robot from the current cell to its right cell
- \(U \): Moves the robot from the current cell to its upper cell
- \(D\): Moves the robot from the current cell to its lower cell
The robot can go to some cell only if it is empty and inside the maze. Therefore, you cannot give a command that takes the robot to an obstacle or out of the maze.
The robot is currently at \((s_x,s_y) \) cell. You want to take it to \((f_x,f_y)\) cell. Therefore, you are required to build a string of character commands that takes the robot to the destination. There may exist several strings that can perform the same task but you must use the string of the minimum length. If there exist several strings of the minimum length, you must select the lexicographically smallest string of them.
Refer to the sample explanation section for better understanding.
Input format
- First line: Two integers \(N\ (3 \le N \le 50)\) and \(M\ (3 \le M \le 50)\)
- Next \(N\) lines: Strings of \(M\) lengths that represent the maze
- Next line: An integer \(Q\ (1 \le Q\le 300)\) denoting the number of queries
- Each of the next \(Q\) lines: Four integers \(s_x\), \(s_y\), \(f_x\), and \(f_y\)
Note: It is guaranteed that \((s_x,s_y)\) and \((f_x,f_y)\) will be empty cells and \((s_x,s_y) \neq (f_x,f_y)\)
Output format
If it is possible to reach the destination, then print the string command as mentioned. Otherwise, print \(Impossible\).
First Query :
There are 2 paths with minimal length.
One is - \((1,3) \rightarrow (1,2) \rightarrow (2,2) \rightarrow (3,2) \rightarrow (3,3)\) , whose string command is LDDR.
The other is - \((1,3) \rightarrow (1,4) \rightarrow (2,4) \rightarrow (3,4) \rightarrow (3,3)\) , whose string command is RDDL.
LDDR is the lexicographically smaller one.
Second Query :
There are 2 paths with minimal length.
One is - \((2,2) \rightarrow (3,2) \rightarrow (3,3) \rightarrow (3,4) \rightarrow (2,4)\) , whose command is DRRU.
The other is - \((2,2) \rightarrow (1,2) \rightarrow (1,3) \rightarrow (1,4) \rightarrow (2,4)\) , whose command is URRD.
DRRU is the lexicographically smaller one.
Third Query :
There is only 1 path with minimal length and it is UUUR.
Fourth Query :
There is no possible path from \((1,1)\) to \((5,1).\)
Fifth Query :
There are so many possible paths from \((1,1)\) to \((5,5)\).
DDRRRRDD is the lexicographically smallest one of them.
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor
Login to unlock the editorial
Please login to use the editor
You need to be logged in to access the code editor
Loading...
Please wait while we load the editor