import java.io.*;
import java.util.StringTokenizer;

public class maze {
  public static void main(String[] args) throws IOException {
    BufferedReader mazeFile  = new BufferedReader(
			        new FileReader("maze.dat") );
    final int N              = Integer.parseInt(mazeFile.readLine());
    byte [][] maze            = new byte[N][N];

    //read file into an array of bytes to save memory...
    StringTokenizer tokens;
    for (int i = 0; i < N; i++) {
      tokens = new StringTokenizer(mazeFile.readLine());
      for (int j = 0; j < N; j++) {
        maze[i][j] = Byte.parseByte(tokens.nextToken());
      }
    }

    //print out the maze before traversal
    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        System.out.print(" " + maze[i][j]);
      }
      System.out.println();
    }

    if (!traverse(maze, 0, 0, 0, 0, N)) System.out.println("No path.");

    for (int i = 0; i < N; i++) {
      for (int j = 0; j < N; j++) {
        System.out.print(" " + maze[i][j]);
      }
      System.out.println();
    }


  }//end main

  public static boolean traverse(byte [][] maze, int i, int j, int Pi, 
				  int Pj, final int N) {

    System.out.println("Trace every move: " + i + " " + j);

    if ( (i==(N-1)) && (j==(N-1)) ) {
      System.out.println("\nWe found the end!");
      System.out.println("Trace back: " + i + " " + j);
      maze[i][j]=9;
      return true;
    }

    boolean success;
    //try north
    if (i == 0)                        success = false;
    else if (maze[i-1][j]==1)          success = false;
    else if ( ((i-1)==Pi) && (j==Pj) ) success = false;
    else success = traverse(maze, i-1, j, i, j, N);
    if (success) {
      System.out.println("Trace back: " + i + " " + j);
      maze[i][j]=9;
      return true;
    }

    //try south
    if (i == N-1)                      success = false;
    else if (maze[i+1][j]==1)          success = false;
    else if ( ((i+1)==Pi) && (j==Pj) ) success = false;
    else success = traverse(maze, i+1, j, i, j, N);
    if (success) {
      System.out.println("Trace back: " + i + " " + j);
      maze[i][j]=9;
      return true;
    }

    //try east
    if (j == N-1)                      success = false;
    else if (maze[i][j+1]==1)          success = false;
    else if ( ((i)==Pi) && (j+1==Pj) ) success = false;
    else success = traverse(maze, i, j+1, i, j, N);
    if (success) {
      System.out.println("Trace back: " + i + " " + j);
      maze[i][j]=9;
      return true;
    }

    //try west
    if (j == 0)                        success = false;
    else if (maze[i][j-1]==1)          success = false;
    else if ( ((i)==Pi) && (j-1==Pj) ) success = false;
    else success = traverse(maze, i, j-1, i, j, N);
    if (success) {
      System.out.println("Trace back: " + i + " " + j);
      maze[i][j]=9;
      return true;
    }

    //By now if it was a "good" square, it will have succeeded.
    //report failure now...
    maze[i][j] = 2;
    return false;


  }// end traverse

}//end class