JOIN
Get Time

   Problem Statement  

 Problem Statement for StepsConstruct

Problem Statement

    There is a rectangular board that is divided into n rows by m columns of cells. Each cell is either empty or it contains an obstacle. You are given the description of the board in the String[] board. Each character in board represents one cell. More precisely, the character board[i][j] represents the cell at coordinates (row i, column j). The character '#' represents an obstacle, the character '.' is an empty cell.



You would like to travel from the top left corner to the bottom right corner of the board in exactly k steps. More precisely, you want to perform the following sequence of actions:



  1. Enter the board by stepping onto the cell at coordinates (0, 0): the top left corner.
  2. Make exactly k steps. In each step, you'll move from your current cell to one of the cells that share a side with your current cell. In other words, in each step you'll go one cell up, down, left, or right.
  3. After the k-th step, you must be in the bottom right corner: at coordinates (n-1, m-1).
Note that you can only step onto empty cells. You have to move in each step, it is not allowed to stay in the same cell. You are allowed to visit each empty cell arbitrarily many times. You are not allowed to leave the board while making the k steps.



You are given the String[] board and the int k. Determine whether it is possible to reach the bottom right corner in the way described above. If there is no solution, return an empty String. If there are some solutions, choose any one of them and return a String containing its description.



If a solution exists, the returned String should consist of k characters, each describing one step. Each character should be one of 'U' (up), 'D' (down), 'L' (left), and 'R' (right).
 

Definition

    
Class:StepsConstruct
Method:construct
Parameters:String[], int
Returns:String
Method signature:String construct(String[] board, int k)
(be sure your method is public)
    
 

Notes

-The character 'U' represents a step that decreases your row number. The character 'L' represents a step that decreases your column number.
 

Constraints

-n, m will be between 2 and 50, inclusive.
-board will contain exactly n elements.
-Each element in board will contain exactly m characters.
-Each character in board will be either '#' or '.'.
-k will be between 1 and 3,000, inclusive.
 

Examples

0)
    
{"...",
 ".#.",
 "..."}
4
Returns: "DDRR"
You need to get from (0,0) to (2,2) in exactly 4 steps.
1)
    
{"...",
 ".#.",
 "..."}
12
Returns: "DDRRUULLDDRR"
This time we want to get there in exactly 12 steps, one possible solution is to go around that obstacle once.
2)
    
{"...#.",
 "..#..",
 ".#..."}
100
Returns: ""
There is no way to get to (n-1, m-1) from (0,0).
3)
    
{"..#",
 "#.#",
 "..#",
 ".#.",
 "..."}
6
Returns: ""
4)
    
{".#...",
 ".#.#.",
 ".#.#.",
 ".#.#.",
 "...#."}
16
Returns: "DDDDRRUUUURRDDDD"
5)
    
{"#.", 
 ".."}
2
Returns: ""
There is no solution because you are not even able to enter the top left cell.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

This problem was used for:
       Single Round Match 707 Sponsored By Blizzard Round 1 - Division II, Level Two