import java.io.*;
import java.util.Scanner;

/**
 * Clase para encontrar la salida de un laberinto (si la hay). 
 * @author ALG
 * @version 1a. ed.
 */
public class Laberinto {
    private int largo;
    private int ancho ;
    private int [][] paredes = {
	{14, 12, 5, 4, 6},
	{10, 9, 4, 3, 10},
	{9, 5, 2, 13, 2},
	{14, 14, 10, 12, 2},
	{9, 1, 1, 3, 11},
    };
    private int [][] visitado;

    /**
     * Constructor por omision. Crea un laberinto de 5*5 determinado
     */
    public Laberinto () {
	largo = 5;
	ancho = 5;
	visitado = new int[5][5];

	for (int i = 0; i < ancho; i++)
	    for (int j = 0; j < largo; j++)
		visitado[i][j] = 0;
    }

    /**
     * Constructor que lee el laberinto de un archivo.
     * @param nombre -- nombre del archivo de texto que contiene el laberinto
     */
    public Laberinto (String nombreArch) throws IOException {
	Scanner in = new Scanner (new File(nombreArch));
	ancho = in.nextInt();
	largo = in.nextInt();
	paredes = new int[ancho][largo];
	visitado = new int[ancho][largo];
	for (int i = 0; i < ancho; i++) {
	    for (int j = 0; j < largo; j++) {
		paredes[i][j] = in.nextInt();
		visitado[i][j] = 0;
	    }
	}
    }

    /**
     * Metodo para encontrar la salida del laberinto
     * @return boolean -- devuelve true si hay salida y false en otro caso
     */
    public boolean encontrarSalida () {
	Punto meta = new Punto (0,0);            // Define la salida
	Pila pila = new Pila(); 
	pila.push(new Punto(largo-1, ancho-1));  // Guarda la entrada
	int contVisitas = 0;

	while (! pila.estaVacia()) {           // Mientras en la pila haya elementos
	    Punto p = (Punto) pila.pop();        // Toma el elemento del tope
	    int x = p.obtenerX();
	    int y = p.obtenerY();
	    if (visitado[x][y] == 0) {        // Si no esta visitado
		visitado[x][y] = ++contVisitas;  // se marca como visitado
		mostrar();
		if (p.equals(meta))
		    return true;   // Se llego a la salida
		guardarVecinos(x, y, pila);  // se guardan los vecinos
		try {Thread.sleep(200);} catch (Exception e) { }
	    }
	}
	return false;   // No puede llegar a la salida
    }

    /*
     * Metodo privado pra guardar en la pila las posiciones vecinas a las 
     * que se puede acceder a partir del punto dado
     * @param x -- coordenada x del punto dado
     * @param y -- coordenada y del punto dado
     * @param pila -- pila en la que se guardan los vecinos
     */
    private void guardarVecinos (int x, int y, Pila pila) {
	if ((paredes[x][y] & 1) == 0)
	    pila.push(new Punto(x+1, y));
	if ((paredes[x][y] & 2) == 0)
	    pila.push(new Punto(x, y+1));
	if ((paredes[x][y] & 4) == 0)
	    pila.push(new Punto(x-1, y));
	if ((paredes[x][y] & 8) == 0)
	    pila.push(new Punto(x, y-1));
    }

    /**
     * Metodo para mostarar la salida del laberinto, si la hay.
     */
    public void mostrar() {
	System.out.println("El laberinto original tiene:");
	for(int i = 0; i < largo; i++){
	    for (int j = 0; j < ancho; j++)
		System.out.print(paredes[i][j]+ " ");
	    System.out.println();
	}

	System.out.println("\nSolución:\n");
	for(int i = 0; i < largo; i++){
	    for (int j = 0; j < ancho; j++)
		System.out.print(visitado[i][j]+ " ");
	    System.out.println();
	}
    }

    public static void main (String [] pps) {
	try {
	    Laberinto mundo = (pps.length != 1) ? new Laberinto(): new Laberinto(pps[0]);
	    mundo.mostrar(); 
	    mundo.encontrarSalida();
	} catch (IOException e) {
	    System.out.println("Error en el archivo "+ pps[0]);
	}
    }
}