import edu.princeton.cs.algs4.DijkstraSP;
import edu.princeton.cs.algs4.DirectedEdge;
import edu.princeton.cs.algs4.EdgeWeightedDigraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.StdOut;

public class Maze {

	public static void main(String[] args) {


		String[] lines = new In("maze.txt").readAllLines();
		int l = 0;
		int c = 0;
		int hnutar = 0;
		int I = 0;
		int U = 0;
		int[][] hnitakerfi = new int[lines.length][lines[0].length()];
		for (String s : lines){
			for(int i = 0; i < lines[0].length(); i++){
				if (s.charAt(c) == 'X'){
					hnitakerfi[l][c] = -1;
				}
				else if (s.charAt(c) == '='){
					hnitakerfi[l][c] = 2;
				}
				else if (s.charAt(c) == '-'){
					hnitakerfi[l][c] = 1;
				}
				else if (s.charAt(c) == 'I'){
					hnitakerfi[l][c] = 0;
					I = 10*l+c;
				}
				else if (s.charAt(c) == 'U'){
					hnitakerfi[l][c] = 1;
					U = 10*l+c;
				}
				c++;
				hnutar++;
			}
			l++;
			c = 0;
		}

		EdgeWeightedDigraph net =  new EdgeWeightedDigraph(hnutar);

		for(int i = 0; i<lines.length; i++){
		    for(int j = 0; j<lines[0].length(); j++){
		    	if(hnitakerfi[i][j] != -1){
		    		if (i != 0 && hnitakerfi[i-1][j] != -1){
		    			DirectedEdge e = new DirectedEdge(10*i+j,10*i+j-10,(double) hnitakerfi[i-1][j]);
		    			net.addEdge(e);
		    		}
		    		if (j != 0 && hnitakerfi[i][j-1] != -1){
		    			DirectedEdge e = new DirectedEdge(10*i+j,10*i+j-1,(double) hnitakerfi[i][j-1]);
		    			net.addEdge(e);
		    		}

		    		if (i != lines.length-1 && hnitakerfi[i+1][j] != -1){
		    			DirectedEdge e = new DirectedEdge(10*i+j,10*i+j+10,(double) hnitakerfi[i+1][j]);
		    			net.addEdge(e);
		    		}
		    		if (j != lines[0].length()-1 && hnitakerfi[i][j+1] != -1){
		    			DirectedEdge e = new DirectedEdge(10*i+j,10*i+j+1,(double) hnitakerfi[i][j+1]);
		    			net.addEdge(e);
		    		}
		    	}
		    }

		}

		DijkstraSP styst = new DijkstraSP(net, I);
		for (DirectedEdge e : styst.pathTo(U)) {
            StdOut.print("(" + e.from()/10 + "," + e.from()%10 + ") -> (" + e.to()/10 + "," + e.to()%10 + ")");
            StdOut.println();
        }
        StdOut.println();



	}
}