// MazeSolver: Find a path through a Maze
// Hao Jiang, March 2008 at BC
// 
// Dependence: StdDraw.java and StdIn.java
// Compile: javac MazeSolver.java 
// Usage: java MazeSolver < maze.txt


public class MazeSolver {
	public static boolean findPath(int[][] maze, int N, int r, 
			               int c, int u, int v)
	{
		if (r == u && c == v) 
		{
			return true;
		}

		maze[r][c] = 1;
	        if (r-1 >= 0 && maze[r-1][c] == 0 && 
			findPath(maze, N, r-1, c, u, v) )
		{
			maze[r-1][c] = 1;
		        connect(r, c, r-1, c, N);
			return true;
		}
		else if (r+1 < N && maze[r+1][c] == 0 && 
			findPath(maze, N, r+1, c, u, v))
		{	
			 maze[r+1][c] = 1;
                         connect(r, c, r+1, c, N);
			 return true;
		}
                else if (c-1 >= 0 && maze[r][c-1] == 0 && 
			findPath(maze, N, r, c-1, u, v))
		{
			 maze[r][c-1] = 1;
                         connect(r, c, r, c-1, N);
			 return true;
		}
                else if (c+1 < N && maze[r][c+1] == 0 && 
			findPath(maze, N, r, c+1, u, v))
	        {  
		  	 maze[r][c+1] = 1;
                         connect(r, c, r, c+1, N);
			 return true;
		}
                else
		{
			maze[r][c] = 3;
                        return false;
		}		
	}

       public static void drawDot(int r , int c, int N)
       {
	       double x = c + 0.5;
	       double y = N - (r + 0.5);
	       StdDraw.setPenRadius(0.1);
	       StdDraw.filledCircle(x, y, 0.1);
       }

       public static void drawCross(int r , int c, int N)
       {
	       double x = c + 0.5;
	       double y = N - (r + 0.5);
	       StdDraw.square(x, y, 0.5);
               StdDraw.line(x-0.5, y-0.5, x+0.5, y+0.5);
               StdDraw.line(x-0.5, y+0.5, x+0.5, y-0.5);
       }

       public static void connect(int r , int c, int u, int v, int N)
       {
	       double x1 = c + 0.5;
	       double y1 = N - (r + 0.5);
	       double x2 = v + 0.5;
	       double y2 = N - (u + 0.5);
               StdDraw.setPenColor(StdDraw.BLUE);
               StdDraw.setPenRadius(0.01);
               StdDraw.line(x1, y1, x2, y2);
               StdDraw.show(100);
       }

        public static void drawMaze(int[][] a)
        {
               
           int rows = a.length;
           int cols = a[0].length;

           for (int i = 0; i < rows; i ++)
           for (int j = 0; j < cols; j ++)
           {
              if (a[i][j] == 2) 
                 drawCross(i, j, rows); 
           } 
           
        }

        public static int[][] loadMaze()
        {
           int N = StdIn.readInt();
           int[][] maze = new int[N][N];

           for (int i = 0; i < N; i++)
           for (int j = 0; j < N; j++) 
               maze[i][j] = StdIn.readInt();

           return maze;
        }
          
	public static void main(String[] args)
	{
		/*int[][] maze = { {50, 0, 2, 0, 0},
			         {2, 0, 0, 0, 0},
				 {2, 2, 0, 2, 0},
				 {0, 0, 0, 0, 100},
				 {2, 2, 0, 0, 2}};
                */

                int[][] maze = loadMaze();

                int startC = 0;
                int startR = 0;
                int endC = 0;
                int endR = 0;
        
                int START = 50;
                int END = 100;
                int N = maze.length;
                for (int i = 0; i < N; i++)
                for (int j = 0; j < N; j++)
                {
                    if (maze[i][j] == START)
                    {
                       startC = j;
                       startR = i;
                       maze[i][j] = 0;
                    }
                    else if (maze[i][j] == END)
                    {
                       endC = j;
                       endR = i;
                       maze[i][j] = 0;
                    }
                }         
           
		StdDraw.setXscale(0, N);
                StdDraw.setYscale(0, N);
                drawMaze(maze);
		drawDot(startR, startC, N);
		drawDot(endR, endC, N);

	        boolean hasPath = findPath(maze, N, startR, startC, 
				           endR, endC);
                
		if (!hasPath)
		  System.out.println("No path!");
	}
}