import java.io.*;

public class Labyrinth {

    public static final int MAX_ROW = 10;
    public static final int MAX_COL = 15;

    private char[][] grid = new char[MAX_ROW][MAX_COL];
    private int startRow, startCol;

    public static final char LEFT  = 'L';
    public static final char RIGHT = 'R';
    public static final char UP    = 'U';
    public static final char DOWN  = 'D';

    public static final char[] MOVES = { LEFT, RIGHT, UP, DOWN };

    public static final char WALL  = '#';
    public static final char EMPTY = ' ';
    public static final char PATH  = '.';

    public static final char IN    = 'I';
    public static final char OUT   = 'O';

    private static String newline = System.getProperty("line.separator");

    // queue-based implementation of solve

public boolean solve(int solutionSize) {

    findStartPos();

    LinkedQueue q = new LinkedQueue();
    String newpath = "";
    q.enqueue(newpath);
    boolean solved = false;
    boolean unsolvable = false;

    while (!solved && !unsolvable) {
        if (q.isEmpty() || q.isFull())
            unsolvable = true;
        else {
            String path = (String) q.dequeue();
            for (int m=0; (m < MOVES.length) &&
                          (! solved) && 
                          (! unsolvable) ; m++) {
                newpath = path + MOVES[m];
                if (checkPath(newpath))
                    if (reachesGoal(newpath))
                        solved = true;
                    else
                        if (q.isFull())
                            unsolvable = true;
                        else if (newpath.length() 
                                  <= solutionSize)
                            q.enqueue(newpath);
            }
        }
    }
    if (solved)
        trace(newpath);
    return solved;
}

    private void findStartPos() {
	for (int row=0; row < MAX_ROW; row++)
	    for (int col=0; col < MAX_COL; col++)
		if (grid[row][col] == IN) {
		    startRow = row;
		    startCol = col;
		    return;
		}
    }

    private void trace(String path) {

	System.out.println("solution = " + path);

	int row = startRow;
	int col = startCol;
	for (int pos=0; pos < path.length(); pos++) {
	    char direction = path.charAt(pos);
	    switch (direction) {
	    case LEFT:  col--; break;
	    case RIGHT:	col++; break;
	    case UP:	row--; break;
	    case DOWN:	row++;break;
	    }
	    grid[row][col] = PATH;
	}
    }

    private boolean reachesGoal(String path) {
	int row = startRow;
	int col = startCol;
	for (int pos=0; pos < path.length(); pos++) {
	    char direction = path.charAt(pos);
	    switch (direction) {
	    case LEFT:  col--; break;
	    case RIGHT:	col++; break;
	    case UP:	row--; break;
	    case DOWN:	row++; break;
	    }
	}
	return grid[row][col] == OUT;
    }

    private boolean checkPath(String path) {
	int row, col;

	boolean[][] visited = new boolean [MAX_ROW][MAX_COL] ;
	for (row=0; row < MAX_ROW; row++) {
	    for (col=0; col < MAX_COL; col++) {
		visited[row][col] = false ;
	    }
	}

	row = startRow;
	col = startCol;
	int pos=0;
	boolean valid = (grid[row][col] == IN);
	visited[row][col] = true;
	while (valid && pos < path.length()) {
	    char direction = path.charAt(pos++);
	    switch (direction) {
	    case LEFT:
		col--;
		break;
	    case RIGHT:
		col++;
		break;
	    case UP:
		row--;
		break;
	    case DOWN:
		row++;
		break;
	    default:
		valid = false;
	    }
	    if ((row >= 0) && (row < MAX_ROW) && (col >= 0) && (col < MAX_COL))
		if (visited[row][col] || grid[row][col] == WALL)
		    valid = false;
		else
		    visited[row][col] = true;
	    else
		valid = false;
	}

	return valid;
    }

    // access methods

    public void set(String input) throws LabyrinthFormatException {

	BufferedReader in = new BufferedReader(new StringReader(input));

	String line;
	int row, col;

	boolean hasIn, hasOut;

	hasIn = hasOut = false;
	row = 0;
	try {
	    while ((line = in.readLine()) != null) {
		if (line.length() != MAX_COL)
		    throw new LabyrinthFormatException("line " + row + "too long:" + line.length());
		if (row >= MAX_ROW)
		    throw new LabyrinthFormatException("too many lines: " + row);
		col = 0;
		for (int i=0; i<MAX_COL; i++) {
		    char c = line.charAt(i);
		    if (c == IN)
			hasIn = true;
		    else if (c == OUT)
			hasOut = true;
		    else if (c != WALL && c != EMPTY)
			throw new LabyrinthFormatException("illegal character: " + c);
		    grid[row][col++] = c;
		}
		row++;
	    }
	} catch (IOException e) {
	    throw new LabyrinthFormatException("error reading input: " + e.getMessage());
	}
	if (!hasIn)
	    throw new LabyrinthFormatException("does not have an input symbol");
	if (!hasOut)
	    throw new LabyrinthFormatException("does not have an output symbol");
	
    }

    public String get() {
	StringBuffer output = new StringBuffer("");
	for (int row=0; row < MAX_ROW; row++) {
	    for (int col=0; col < MAX_COL; col++)
		output.append(grid[row][col]);
	    if (row < (MAX_ROW-1))
		output.append(newline);
	}
	return output.toString();
    }

}