The first problem of this practice session is pretty easy and standard – you have to find your way through a maze.
Problem specification
You are given a description of a maze. Produce a short sequence of moves that exits it.
Input specification
The first line of the input contains two positive integers R and C – the number of rows and columns in the maze. Rows are numbered 1 to R, and columns 1 to C.
R lines follow. Each of them contains C integers. The c-th integer in the r-th row is 0 if the cell at (r,c) is free, and it is 1 if the cell at (r,c) is a wall.
In the final line are the coordinates of the cell where you start.
Output specification
The output shall contain any sequence of at most 200 moves. The input will be such that at least one such sequence will exist.
All moves must be valid (i.e., may not crash into a wall), and the last move must be the only move that exits the maze.
Describe the moves using letters U for up, D for down, L for left and R for right. (Up is the direction in which row numbers decrease, left is the direction in which column numbers decrease.)
You may separate the moves in the output by whitespace.
Flash version
For your convenience, we provide Flash applications in which you can traverse the given mazes using your
keyboard. If you successfully exit the maze, the application will print your sequence of moves, you can simply
copy it and submit it.
Easy maze.
Hard maze.
Example
| input
7 9
1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 0 1 1 0 1 0 0 0 1 0 0 1 0 1 1 1 0 1 0 1 1 0 0 0 0 0 1 0 1 1 1 1 1 1 1 1 1 1 6 2 |
| output
R L U U U U R R R
R R R D D D U R R |