import java.util.Random;
import java.util.Scanner;

public class uke_7_1_c
{
    // Verdiene som kan lagres i labyrinten
    int STENGT = 0, FRI = -1, BRUKT = -2;
    
    // Størrelse på kvadratisk labyrint og 2D-tabell som lagrer
    // labyrinten
    int n;
    int L[][];

    int antSteg; // Antall steg på løsningsveien
    
    // Konstruktør som oppretter en tilfeldig labyrint med en gitt
    // prosentandel blokkerte ruter
    public uke_7_1_c(int n, int prosentBlokkert)
    {
	this.n = n;
	antSteg = 0;
	L = new int[n][n];
	Random R = new Random();
	for (int i = 0; i < n; i++)
	    for (int j = 0; j < n; j++)
		if (R.nextInt(100) < prosentBlokkert)
		    L[i][j] = STENGT;
		else
		    L[i][j] = FRI;
    }

    
    // Funksjonen finnVei leter rekursivt etter en vei gjennom
    // labyrinten fra rute (i,j) til rute (n-1,n-1).
    // Returnerer true hvis vi fant en slik vei, false ellers
    boolean finnVei(int i, int j)
    {
	// Markerer at rute (i,j) nå er oppsøkt
	L[i][j] = BRUKT;

	// Bunn i rekursjonen: Ferdig hvis vi er i nedre høyre hjørne
	if (i == n-1 && j == n-1)
	{
	    // Lagrer siste steg på veien
	    antSteg++;
	    L[i][j] = antSteg;
	    return true;
	}
	
	// Prøver alle fire mulige lovlige veier videre fra rute (i,j)
	// i denne rekkefølgen: 1. Høyre, 2. Ned , 3. Venstre, 4. Opp
	int dI[] = {  0,  1,  0, -1};
	int dJ[] = {  1,  0, -1,  0};

	for (int k = 0; k < 4; k++)
	{
	    int nyI = i + dI[k];
	    int nyJ = j + dJ[k];

	    // Sjekker om det er lovlig å gå til ny posisjon
	    if (nyI >=0 && nyI < n && nyJ >=0 && nyJ < n && L[nyI][nyJ] == FRI)
	    {	    
		// Prøver å finne vei videre rekursivt
		if (finnVei(nyI, nyJ))
		{
		    // Her vet vi at det ble funnet en vei gjennom
		    // labyrinten fra rute (i,j). Lagrer dette steget
		    // på veien
		    antSteg++;
		    L[i][j] = antSteg;
		    return true;
		}
	    }
	}
	// Hvis vi kommer hit i koden, fantes det ingen vei gjennom
	// labyrinten fra rute (i,j), returnerer false
	return false;
    }

    
    // Skriver ut funnet vei 
    public String toString()
    {
        String result = "\n";
        for (int i = n-1; i >= 0; i--)
        {
	    for (int j = n-1; j >= 0; j--)
		if (L[i][j] == FRI || L[i][j] == BRUKT)
		    result += "__ ";
		else if (L[i][j] == STENGT)
		    result += "XX ";
		else if (L[i][j] < 10)
		    result += " " + L[i][j] + " ";
		else
		    result += L[i][j] + " " ;
            result += "\n";
        }
        return result;
    }

    // Testprogram
    public static void main(String argv[])
    {
	// Leser størrelsen på labyrinten og prosentandel blokkerte ruter
	Scanner scanner = new Scanner(System.in);
	System.out.print("n?: ");
	int n = scanner.nextInt();
	System.out.print("% blokkerte ruter?: ");
	int prosentBlokkert = scanner.nextInt();

	// Oppretter ny labyrint
	uke_7_1_c lab = new uke_7_1_c(n, prosentBlokkert);
	
	// Leter etter vei fra øvre venstre hjørne
	boolean funnetVei = lab.finnVei(0, 0);
	
	// Skriver ut evt. funnet vei
	if (funnetVei)
	    System.out.println(lab);
	else
	    System.out.println("Fant ingen vei gjennom labyrinten");
    }
}