import java.util.*;

class GLaby {

    static final Scanner input = new Scanner(System.in);
    static final Random random = new Random();

    /**
     * Pour l'affichage graphique, la taille d'une case (pixels) et l'intervalle
     * entre deux cases
     */
    static final int TCASE = 5;
    static final int INTER = 1;

    /**
     * Les différents états possibles d'une case :
     *   MUR      il y a un mur
     *   VIDE     il n'y a rien
     *   CONSTR   case constructible
     *   CHOK     sur le bon chemin
     *   CHVU     (mauvais) chemin déjà exploré
     *
     * On utilise ici une énumeration pour définir un nouveau type ayant pour
     * valeurs ces constantes.  Cf. tout bon manuel de Java pour les détails.
     */
    enum Case { MUR, VIDE, CONSTR, CHOK, CHVU };

    /**
     * Retourne `true' si la case (i, j) est constructible
     */
    static boolean estConstructible(Case[][] laby, int i, int j) {
        // dimensions du labyrinthe
        final int N = laby.length;
        final int M = laby[0].length;

        return
            // la case n'est pas déjà construite
            (laby[i][j] != Case.MUR) &&
            // la case n'est pas au bord
            (i > 0 && i < N - 1 && j > 0 && j < M - 1) &&
            ( // la case à droite est un mur ?
              ( laby[i][j+1] == Case.MUR   && laby[i-1][j] != Case.MUR &&
                laby[i-1][j-1] != Case.MUR && laby[i][j-1] != Case.MUR &&
                laby[i+1][j-1] != Case.MUR && laby[i+1][j] != Case.MUR ) ||
              // la case au dessus est un mur ?
              ( laby[i-1][j] == Case.MUR   && laby[i][j-1] != Case.MUR &&
                laby[i+1][j-1] != Case.MUR && laby[i+1][j] != Case.MUR &&
                laby[i+1][j+1] != Case.MUR && laby[i][j+1] != Case.MUR ) ||
              // la case à gauche est un mur ?
              ( laby[i][j-1] == Case.MUR   && laby[i+1][j] != Case.MUR &&
                laby[i+1][j+1] != Case.MUR && laby[i][j+1] != Case.MUR &&
                laby[i-1][j+1] != Case.MUR && laby[i-1][j] != Case.MUR ) ||
              // la case au dessous est un mur ?
              ( laby[i+1][j] == Case.MUR && laby[i][j+1] != Case.MUR &&
                laby[i-1][j+1] != Case.MUR && laby[i-1][j] != Case.MUR &&
                laby[i-1][j-1] != Case.MUR && laby[i][j-1] != Case.MUR ) );
    }

    /**
     * Recherche la `k'-ième case (k >= 1) dans `laby' ayant la valeur
     * `val'.  Ne considère pas les cases du bord.  Les coordonnées de la
     * case trouvée sont retournées par un tableau de deux entiers.
     * Retourne { -1, -1 } si la case en question n'existe pas.
     */
    static int[] trouveCase(Case[][] laby, int k, Case val) {
        // dimensions du labyrinthe
        final int N = laby.length;
        final int M = laby[0].length;

        int[] res = { -1, -1 };
    recherche:
        for (int i = 1 ; i < N - 1 ; i++) {
            for (int j = 1 ; j < M - 1 ; j++) {
                if (laby[i][j] == val)
                    k--;
                if (k == 0) {
                    res[0] = i;
                    res[1] = j;
                    break recherche;
                }
            }
        }
        return res;
    }

    /**
     * Initialise le labyrinthe : place un mur tout autour, sauf à l'entrée et à
     * la sortie dont les coordonnées sont données par (Ei, Ej) pour l'entrée,
     * et (Si, Sj) pour la sortie.
     */
    static void initLaby(Case[][] laby, int Ei, int Ej, int Si, int Sj) {
        // dimensions du labyrinthe
        final int N = laby.length;
        final int M = laby[0].length;

        for (int i = 0 ; i < N ; i++) {
            for (int j = 0 ; j < M ; j++) {
                if ( (i == 0 || i == N - 1 || j == 0 || j == M - 1) &&
                     (i != Ei || j != Ej) && (i != Si || j != Sj) )
                    laby[i][j] = Case.MUR;
                else
                    laby[i][j] = Case.VIDE;
            }
        }
    }

    /**
     * Place `ngraines' graines de manière aléatoire.
     */
    static void placeGraines(Case[][] laby, int ngraines) {
        // dimensions du labyrinthe
        final int N = laby.length;
        final int M = laby[0].length;

        int nvides = (N - 2) * (M - 2); // le nombre de cases vides
        if (ngraines > nvides)
            ngraines = nvides;
        while (ngraines-- > 0) {
            // choisit une case de manière aléatoire parmi les cases vides
            int[] c = trouveCase(laby, 1 + random.nextInt(nvides), Case.VIDE);
            int i = c[0];
            int j = c[1];
            // construit un mur sur cette case
            laby[i][j] = Case.MUR;
            nvides--;
        }
    }

    /**
     * Marque et dénombre les cases constructibles.  Retourne leur nombre.
     */
    static int marqueCons(Case[][] laby) {
        // dimensions du labyrinthe
        final int N = laby.length;
        final int M = laby[0].length;

        int ncons = 0;              // le nombre de cases constructibles
        // NB: les cases du bord ne sont pas constructibles, il est
        // inutile de les tester
        for (int i = 1 ; i < N - 1; i++) {
            for (int j = 1 ; j < M - 1; j++) {
                if (estConstructible(laby, i, j)) {
                    laby[i][j] = Case.CONSTR;
                    ncons++;
                }
            }
        }
        return ncons;
    }

    /**
     * Dessine la case de coordonnées (i, j)
     */
    static void dessineCase(DrawingWindow w, Case[][] laby, int i, int j) {
        // dimensions du labyrinthe
        final int N = laby.length;
        final int M = laby[0].length;

        // coordonnées graphiques du carré représentant la case
        int xmin = INTER + j * (TCASE + INTER);
        int xmax = (j + 1) * (TCASE + INTER) - 1;
        int ymin = INTER + i * (TCASE + INTER);
        int ymax = (i + 1) * (TCASE + INTER) - 1;

        switch (laby[i][j]) {
        case MUR:
            w.setColor("black");
            break;
        case VIDE:
        case CONSTR:
            w.setColor("white");
            break;
        case CHOK:
            w.setColor("lime");
            break;
        case CHVU:
            w.setColor("silver");
            break;
        }
        w.fillRect(xmin, ymin, xmax, ymax);
        if (laby[i][j] == Case.CONSTR) {
            w.setColor("black");
            w.drawLine(xmin, ymin, xmax, ymax);
            w.drawLine(xmin, ymax, xmax, ymin);
        }
    }

    /**
     * Recherche un chemin depuis la case de coordonnées (i, j) jusqu'à la
     * case de coordonnées (si, sj).  Marque les cases déjà visitées pour
     * éviter d'y passer plusieurs fois.
     * Stratégie récursive naïve.
     */
    static boolean rechercheChemin(DrawingWindow w, Case[][] laby,
                                   int i, int j, int si, int sj) {
        // dimensions du labyrinthe
        final int N = laby.length;
        final int M = laby[0].length;

        // si la case n'existe pas, contient un mur ou a déjà été visitée,
        // on n'a pas trouvé le chemin
        if (i < 0 || i >= N || j < 0 || j >= M || laby[i][j] != Case.VIDE)
            return false;

        // affiche la case comme faisant partie du chemin
        laby[i][j] = Case.CHOK;
        dessineCase(w, laby, i, j);
        w.sync();

        // a-t-on trouvé la sortie ?
        if (i == si && j == sj)
            return true;

        // non, on essaie les différentes directions dans un ordre aléatoire
        int[] direction = { 0, 1, 2, 3 };
        int k, kmax;
        boolean trouve = false;
        for (kmax = 4 ; !trouve && kmax > 0 ; kmax--) {
            k = random.nextInt(kmax);
            switch (direction[k]) {
            case 0:
                trouve = rechercheChemin(w, laby, i + 1, j, si, sj);
                break;
            case 1:
                trouve = rechercheChemin(w, laby, i, j + 1, si, sj);
                break;
            case 2:
                trouve = rechercheChemin(w, laby, i - 1, j, si, sj);
                break;
            case 3:
                trouve = rechercheChemin(w, laby, i, j - 1, si, sj);
                break;
            }
            direction[k] = direction[kmax - 1];
        }

        // si le chemin n'a pas été trouvé, marque la case comme vue
        if (!trouve) {
            laby[i][j] = Case.CHVU;
            dessineCase(w, laby, i, j);
            w.sync();
        }
        return trouve;
    }

    /**
     * Construit le labyrinthe et l'affiche au fur et à mesure.
     */
    static void genereEtAfficheLaby(DrawingWindow w, Case[][] laby) {
        // dimensions du labyrinthe
        final int N = laby.length;
        final int M = laby[0].length;

        int ncons = marqueCons(laby); // le nombre de cases constructibles

        // dessine toutes les cases dans leur état initial
        w.setBgColor("white");
        w.clearGraph();
        for (int i = 0 ; i < N ; i++)
            for (int j = 0 ; j < M ; j++)
                dessineCase(w, laby, i, j);
        w.sync();

        while (ncons > 0) {
            // choisit une case de manière aléatoire parmi les cases
            // constructibles
            int[] c = trouveCase(laby, 1 + random.nextInt(ncons), Case.CONSTR);
            int i = c[0];
            int j = c[1];
            // construit un mur sur cette case
            laby[i][j] = Case.MUR;
            dessineCase(w, laby, i, j);
            ncons--;
            // met à jour les huit cases autour
            for (int ii = i - 1; ii <= i + 1; ii++) {
                for (int jj = j - 1; jj <= j + 1; jj++) {
                    if (laby[ii][jj] == Case.CONSTR &&
                        !estConstructible(laby, ii, jj)) {
                        laby[ii][jj] = Case.VIDE;
                        dessineCase(w, laby, ii, jj);
                        ncons--;
                    } else if (laby[ii][jj] == Case.VIDE &&
                               estConstructible(laby, ii, jj) ) {
                        laby[ii][jj] = Case.CONSTR;
                        dessineCase(w, laby, ii, jj);
                        ncons++;
                    }
                }
            }
            w.sync();
        }
    }

    public static void main(String[] args) {
        // taille du labyrinthe : N lignes, M colonnes
        final int N = 100;
        final int M = 100;
        int ngraines;

        if (args.length > 0) {
            ngraines = Integer.parseInt(args[0]);
            System.out.println("Nombre de graines : " + ngraines);
        } else {
            System.out.print("Nombre de graines ? ");
            ngraines = input.nextInt();
        }

        DrawingWindow w = new DrawingWindow("Labyrinthe",
                                            INTER + M * (TCASE + INTER),
                                            INTER + N * (TCASE + INTER));
        Case[][] labyrinthe = new Case[N][M];

        // coordonnées de l'entrée du labyrinthe
        int Ei;
        int Ej;
        if (random.nextBoolean()) {
            // entrée en haut
            Ei = random.nextInt(N - 2) + 1;
            Ej = 0;
        } else {
            // entrée sur la gauche
            Ei = 0;
            Ej = random.nextInt(M - 2) + 1;
        }

        // coordonnées de la sortie du labyrinthe
        int Si;
        int Sj;
        if (random.nextBoolean()) {
            // sortie en bas
            Si = random.nextInt(N - 2) + 1;
            Sj = (M - 1);
        } else {
            // sortie sur la droite
            Si = (N - 1);
            Sj = random.nextInt(M - 2) + 1;
        }

        initLaby(labyrinthe, Ei, Ej, Si, Sj);
        placeGraines(labyrinthe, ngraines);
        genereEtAfficheLaby(w, labyrinthe);

        System.out.println("-*- Cliquer dans la fenêtre pour continuer -*-");
        w.waitMousePress();

        if (rechercheChemin(w, labyrinthe, Ei, Ej, Si, Sj))
            System.out.println(":-) J'ai trouvé la sortie !");
        else
            System.out.println(":-( Je n'ai pas trouvé la sortie.");
    }
}