Maze solving

,

Problem Statement
You are dropped in a maze which has only one exit point. Given the configuration of the maze and your starting point in the maze print the directions that you will take to reach the exit point. Note that the walkable are of the maze is indiacted by ‘.’, blocked area by ‘X’, your initial point by ‘I’ (Capital i), exit point by ‘E’.

INPUT

First line contains M and N indicating the size of the maze.

Next M lines (each of them) contain N space seperated characters indicating the configuration of the maze.

OUTPUT

Print space seperated characters indicating the directions to reach exit point. Note that there will be only one way possible to reach the exit point and you must print minimum required directions. Note that you can move in any of the 4 directions freely (if allowed) at any point.

U, D, L, R (Up, Down, Left, Right respectively)

SAMPLE

INPUT

2 3

E . I

. X .

OUTPUT

L L

EXPLANATION

Initaially you are at (0,2), assuming the top left corner is (0,0). You can take LEFT or go DOWN, but going DOWN wil not help you. So ou take LEFT and one more LEFT to reach the exit point.

Note that your output must only contain the minimum required directions. For the above example you must not print “D U L L L” even though it takes you to the exit correctly

Category “Here is my problem statement” recognized

Starting from the initial point I, you can perform Breadth First Search to search for the exit. ( If you do not know about the BFS algorithm, first read about it here )
For each block, you need to keep track of its predecessor in the BFS, so that you can reconstruct the path after finding the exit.

EDIT:
Next time please follow these guidelines to post a question.