How to Operate a Robot
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
There is s a square maze consisting of N rows and N columns divided into unit cells. The rows are numbered from the top to the bottom starting from 1, and the columns are numbered from the left to the right also starting from 1.
You have a robot which you have to operate. Initially the robot is located in the upper-left corner of the maze (i.e. at the cell (1, 1)). In a single move you can move the robot in any one of four basic directions: left, right, up or down.
Some cells of the maze are forbidden. It is known that there are no two forbidden cells that share an edge or a corner. The cell (1, 1) is not forbidden.
You have to construct a sequence of moves of the robot satisfying the following conditions.
- Robot never leaves the maze.
- Robot never visits a forbidden cell.
- Robot visits each non-forbidden cell of the maze at least once.
You are interested in finding any valid sequence of moves such that there are no more than three consecutive moves that moved the robot in the same direction eg. 'DDDD' is invalid sequence of moves while 'D' and 'DDD' is valid. Also total number of moves should not be more than N * (N + 7). Please find any such sequence.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains the single integer N.
In the next N lines, each line contains N characters representing the rows of maze. The characters can be one of the following ones:
- '.' denoting a non-forbidden cell.
- '#' denoting a forbidden cell.
For each test case, output a single line containing the answer to the corresponding test case. The answer should be a string of characters 'L', 'R', 'U' and 'D', representing left, right, up and down moves, respectively. The answer for each test case should not contain more than N*(N+7) moves.
- 2 ≤ T ≤ 5
- 2 ≤ N ≤ 1000
- It is guaranteed that there exists a valid sequence of moves containing no more than N * (N + 7) moves.
Input: 2 2 .. .# 3 ... #.. ..# Output: DUR RRDLDL
|Tags||cook56, easy, simulation, witua|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.