import java.util.*;
public class MaizeShortestPath {
	static Coord goal;
	static int minimal;
	static Coord ROOT = new Coord(0,0);
	public static void main(String[] args){
		String input = "OXXO\n" + 
					   "OXOO\n" +
					   "OOXO\n" +
					   "OXOO\n";
		String input2 = "OXXOO\n" + 
		   				"OXOXO\n" +
		   				"OXOOO\n" +
		   				"OOXXO\n";
		String[] arr = {input,input2};
		for(String str : arr){
			Scanner s = new Scanner( str);
			List<char[]> lst = new ArrayList<char[]>();
			int cols = 0;
			while(s.hasNextLine()){
				String line = s.nextLine();
				char[] c = new char[ line.length()];
				for(int i=0;i<c.length;i++) c[i] = line.charAt(i);
				lst.add(c);
				cols = c.length;
			}
			char[][] iArr = new char[lst.size()][cols];
			for(int i=0;i<lst.size();i++)
				iArr[i] = lst.get(i);
			printArray(iArr);
			path.clear();
			goal = new Coord ( iArr.length-1, iArr[0].length -1);
			minimal = goal.x + goal.y + 10;
			start(iArr);
			System.out.println("minimal path length:" + minimal);
		}
	}
	
	static List<Coord> path = new ArrayList<Coord>();
	
	public static void start(char[][] iArr){
		Coord root = new Coord(0,0);
		path.add(root);
		start(iArr,root);
	}
	static void prompt(){
		Scanner s = new Scanner(System.in);
		s.nextLine();
	}
	public static void start(char[][] iArr, Coord root){
		//System.out.println("processing the root:" + root);
		//prompt();
		List<Coord> lst = findChildren(iArr,root);		
		if(lst.size() <= 1 && !root.equals( ROOT )) {
			path.remove(path.size() -1);			
			return;
		}
		// if the root has the goal as a direct child, then finish
		if(lst.indexOf(goal)!=-1){
			minimal = Math.min(minimal, path.size());
			System.out.println("New path:" + path);
			path.remove(path.size()-1);
			return;
		}
		
		int length = 1;
		for(int i=0;i<lst.size();i++){
			Coord newRoot = lst.get(i);			
			if(!isIn(path,newRoot)){
				path.add(newRoot);				
				start(iArr,newRoot);				
			}			
		}		
		int index = path.indexOf(root);
		if(index != -1) path = path.subList(0,index);		
	}
	static HashMap<Coord,Integer> map = new HashMap<Coord,Integer>();
	
	public static boolean isIn(List<Coord> lst, Coord coord){
		return lst.indexOf(coord) != -1;
	}
	
	public static List<Coord> findChildren(char[][] iarr, Coord coord){		
		List<Coord> lst = new ArrayList<Coord>();
		int x = coord.x;
		int y = coord.y;
		int rows = iarr.length;
		int cols = iarr[0].length;
		if(x+1 < rows && iarr[x+1][y] == 'O') lst.add(new Coord(x+1,y));
		if(x-1 >=0 && iarr[x-1][y] == 'O') lst.add(new Coord(x-1,y));
		if(y+1 < cols && iarr[x][y+1] == 'O') lst.add(new Coord(x,y+1));
		if(y-1 >=0 && iarr[x][y-1] == 'O') lst.add(new Coord(x,y-1));
		if(x+1< rows && y+1<cols && iarr[x+1][y+1]=='O') lst.add(new Coord(x+1,y+1));
		if(x-1>=0 && y-1>=0 && iarr[x-1][y-1]=='O') lst.add(new Coord(x-1,y-1));
		if(x-1>=0 && y+1<cols && iarr[x-1][y+1]=='O') lst.add(new Coord(x-1,y+1));
		if(x+1<rows && y-1>=0 && iarr[x+1][y-1]=='O') lst.add(new Coord(x+1,y-1));		
		return lst;		
	}
	

	static void printArray(char[][] mat){
		for(int i=0;i<mat.length;i++){
			for(int j=0;j<mat[i].length;j++) 
				System.out.print(mat[i][j] + " ");
			System.out.println();
		}
		
	}

}

class Coord{
	int x;
	int y;
	public Coord(int x, int y){
		this.x = x;
		this.y = y;
	}
	public String toString(){ return "(" + x + "," + y + ")";}
	public boolean equals(Object obj){
		Coord c = (Coord) obj;
		return c.x == x && c.y == y;
	}
}