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 upperleft 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 nonforbidden 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.
Input
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 nonforbidden cell.
 '#' denoting a forbidden cell.
Output
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.
Constraints
 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.
Example
Input: 2 2 .. .# 3 ... #.. ..# Output: DUR RRDLDL
Author:  witua 
Tester:  iscsi 
Editorial  http://discuss.codechef.com/problems/VISITALL 
Tags  cook56, easy, simulation, witua 
Date Added:  19032015 
Time Limit:  2 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, 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 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 