import java.awt.*;
import java.util.*;

/**
 *
 * Tiu cxi ludo iam (antaux disvastigxo de komputiloj) estis multe ludata
 * de Germanaj, eble ankaux aliaj, lernantoj dum tedaj lernejaj lecionoj.
 * La reguloj estas simplaj:
 * <UL>
 * <LI>
 * Cxiu ludanto estas sxiparestro (aux admiralo, se vi preferas).
 * Unue cxiu ludanto desegnas por si kampon (maron) de 10 x 10 kvadratoj,
 * kaj en tiun kampon metas dek sxipojn:
 *     <UL>
 *     <LI> kvar kun unu kvadrato
 *     <LI> tri kun du kvadratoj
 *     <LI> du kun tri kvadratoj
 *     <LI> unu kun kvar kvadratoj
 *     </UL>
 *     La kvadratoj de unu sxipo devas esti koneksaj horizontale aux vertikale;
 *     ne suficxas diagonala konekseco.
 *     (Tio estas malpli strikta kondicxo ol en aliaj variajxoj,
 *      kie sxipo devas esti unudimensiaj vicoj.)
 *     Du sxipoj devas ne tusxi unu la alian,
 *     nek horizontale, nek vertikale, nek diagonale.
 *     <P>
 *     Ne eblas vidi la sxipojn de la kontrauxulo;
 *     eble ili estas tro malproksimaj,
 *     aux estas nokto, aux temas pri submaraj sxipoj.
 *     <P>
 *     Cxi-supre la maldekstra kvadrato apartenas al vi, la dekstra estas de la
 *     komputilo. Metu viajn sxipojn klakante per la muso (maldekstre).
 *     Cxe la pli grandaj sxipoj, flavaj punktoj montras al vi la disponeblajn
 *     kvadratojn.
 * <LI>Poste la ludantoj alterne "pafas" al la kontrauxula kampo,
 *     indikante iun kvadraton (ankoraux nepafitan).
 *     La ludanto simple alklakas la kvadraton (dekstre) per la muso.
 *     Trafitaj sxipoj estas markitaj (anoncitaj).
 *     Komplete detruitaj ("sinkigitaj") sxipoj estas markitaj per rugxa koloro.
 * <LI>Malgajnas tiu, kiu perdas sian lastan sxipon, kompreneble.
 * </UL>
 */
public class Sxiparestro extends java.applet.Applet {
    private GridBagLayout arangxo = new GridBagLayout();
    private GridBagConstraints c = new GridBagConstraints();
    /** la sxiparo de la komputilo. */
    private Sxiparo      miajSxipoj;
    /** la sxiparo de la kontrauxulo (la homa ludanto). */
    private GxiaSxiparo gxiajSxipoj;
    /** kampo por mesagxoj al la ludanto. */
    private TextField   mesagxo = new TextField();
    /** butono por rekomenci la ludon. */
    private Button      buRekomencu = new Button("rekomencu");
    private boolean     finita = false;
    /** konstanto, kiu indikas la longecon / largxecon de la kampo. */
    private final int   n = 10;
    public  boolean     estasFinita() { return finita; }

    /**
     * Konstruas novan lud-objekton.
     */
    public Sxiparestro() {
    }

    /**
     * La programeto komencigxas.
     * Videbligu la fenestron kaj ekludu!
     */
    public void init() {
        setLayout( arangxo );

        show();
        ludu();
    }

    /**
     * Komencas novan ludon.
     * Unue konstruas du sxiparo-objektojn,
     * poste kunmetas la strukturon de la fenestro (surfaco).
     */
    private final void ludu() {
        removeAll();

        miajSxipoj  = new     Sxiparo( n, this );
        gxiajSxipoj = new GxiaSxiparo( n, this );

        c.fill    = GridBagConstraints.BOTH;
        c.anchor  = GridBagConstraints.NORTHWEST;
        c.gridwidth = 1;
        c.weightx = 1.0;
        c.weighty = 1.0;
        c.gridx   = GridBagConstraints.RELATIVE;
        c.gridy   = 0;
        arangxo.setConstraints(miajSxipoj, c);
        arangxo.setConstraints(gxiajSxipoj, c);
        c.gridx   = 0;
        c.gridy   = GridBagConstraints.RELATIVE;
        c.gridwidth = 2;
        c.weighty = 0.0;
        arangxo.setConstraints(mesagxo, c);
        c.gridy   = GridBagConstraints.RELATIVE;
        arangxo.setConstraints(buRekomencu, c);

        add( gxiajSxipoj );
        add( miajSxipoj );
        add( mesagxo );
        add( buRekomencu );

        finita = false;

        layout();
    }

    /**
     * La kontrauxulo faris esplormovon ("pafis").
     * Necesas reagi:
     * - se mi estas venkita, gratulu la venkinton.
     * - alie mi mem pafas; poste mi kontrolas, cxu eble venkis mi.
     */
    public void gxiAgis() {
        // gxi faris esplormovon
        if( miajSxipoj.venkita() ) {
            finita = true;
            mesagxu("Vi venkis. Gratulon!");
        }
        else {
            gxiajSxipoj.faruEsploron();
            if( gxiajSxipoj.venkita() ) {
                finita = true;
                mesagxu("Mi venkis.");
            }
        }
    }

    /**
     * Eldonu mesagxon en la teskt-kampo.
     */
    public void mesagxu( String s ) {
        mesagxo.setText( s );
    }

    /**
     * Se la uzanto pusxis la butonon "rekomencu", komencu novan ludon.
     */
    public boolean action( Event e, Object o ) {
        if( e.target == buRekomencu )
            ludu();
        return super.action( e, o );
    }
};

/**
 * klaso "Sxiparo" administras sxiparon kaj montras gxin sur la ekrano.
 */

class Sxiparo extends Canvas {
                                /** kampo kun sxipo */
    protected final int SX = 1;
                                /** kampo apud sxipo */
    protected final int AP = 2;
                                /** kampo kun maro */
    protected final int MA = 0;
                                /** kandidato por aparteni al sxipo */
    protected final int KA = 3;
                                /** nova sxipo (konstruata) */
    protected final int SX0 = 11;
                                /** kampo apud nova sxipo */
    protected final int AP0 = 12;
                                /** konstanto adiciebla al aliaj valoroj,
                                 *  indikas, ke al tiu kampeto estis pafite */
    protected final int PAF = 32;

                                /** kampo kun trafita sxipo */
    protected final int TR = SX | PAF;
                                /** kampo kun sinkigita sxipo */
    protected final int SI =  5 | PAF;
                                /** maltrafo */
    protected final int MT = MA | PAF;

    /** longeco / largxeco de unu ludkampeto */
    protected int d = 16;
    /** dikeco de la kadro */
    protected int k = 1;

    /** longeco / largxeco de la tuta ludkampo */
    protected int n;
    protected int[][] sxipoj;
    protected Sxiparestro estro;
    /**
     * Cxu tiu sxiparo estas videbla por la uzanto?
     * La proprajn li vidu, tiujn de la komputilo ne!
     */
    protected boolean sxipojVideblaj = false;
    /** Cxu la sxiparo jam estas kompleta? */
    protected boolean kompleta = false;
    /** Cxu la sxiparo jam estas kompleta? */
    public boolean estasKompleta() { return kompleta; }

    /**
     * Konstruas novan sxiparon.
     * Konstruu 
     * <UL>
     * <LI>kvar sxipojn de grandeco 1</LI>
     * <LI>tri  sxipojn de grandeco 2</LI>
     * <LI>du   sxipojn de grandeco 3</LI>
     * <LI>unu  sxipon  de grandeco 4</LI>
     * </UL>
     */
    public Sxiparo( int n, Sxiparestro estro ) {
        this.n = n;
        this.estro = estro;

        sxipoj = new int[n][n];
        metuSxipon( 1 );
        metuSxipon( 1 );
        metuSxipon( 1 );
        metuSxipon( 1 );
        metuSxipon( 2 );
        metuSxipon( 2 );
        metuSxipon( 2 );
        metuSxipon( 3 );
        metuSxipon( 3 );
        metuSxipon( 4 );

        kompleta = true;

        repaint();
    }

    /**
     * Donu minimuman grandecon por la ludkampo.
     * Cxiu kampeto havu almenaux 4 x 4 bilderojn.
     */
    public Dimension minimumSize() {
        return new Dimension(4*n, 4*n);
    }   

    /**
     * Pentru la kampon (maron).
     */
    public void paint( Graphics g ) {
        int am = Math.min( size().width - 10, size().height );
        d = am / n;
        int dd = d/4;
        for( int y= n-1; y >= 0; y-- ) {
            int yk = y*d + k;
            for( int x= 0; x < n; x++ ) {
                int val = sxipoj[x][y];
                int xk = x*d + k;
                g.setColor( val == SI ? Color.red
                          : val == TR ? Color.white
                          : val == SX && estro.estasFinita() ? Color.yellow
                          : val == SX && sxipojVideblaj ? Color.white
                          : val == SX0 && sxipojVideblaj ? Color.white
                          : Color.blue );
                g.fillRect( xk+1, yk+1, d-1, d-1 );

                int paf = sxipoj[x][y] & PAF;
                if( paf != 0 ) {
                    g.setColor( Color.black );
                    g.fillOval( xk+dd, yk+dd, d-2*dd, d-2*dd );
                }
                else if( val == KA && sxipojVideblaj ) {  // montru la kandidatojn:
                    g.setColor( Color.yellow );
                    g.fillOval( xk+dd, yk+dd, d-2*dd, d-2*dd );        
                }
            }
        }

        desegnuKadron( g );
    }

    /**
     * Desegnu kadron cxirkaux la kampo.
     * Se la ludanto malvenkis, trastreku gxin diagonale.
     */
    protected void desegnuKadron( Graphics g ) {
        int a = n*d + 2*k;
        g.setColor( Color.black );
        g.drawLine( 0, 0, a, 0 );
        g.drawLine( 0, 0, 0, a );
        g.setColor( Color.white );
        g.drawLine( 0, a, a, a );
        g.drawLine( a, 0, a, a );

        if( venkita() ) {
            g.setColor( Color.red );
            g.drawLine( 0, 0, a, a );
            g.drawLine( 0, a, a, 0 );
        }
    }

    public void update( Graphics g ) {
        g.clearRect( n*d, 0, size().width-n*d, size().height);
        paint( g );
    }

    /**
     * La uzanto klakis per la muso!
     * Kalkulu la koordinatoj de la trafita kampo kaj pafu!
     */
    public boolean mouseDown( Event e, int xx, int yy ) {
        int x = xx / d;
        int y = yy / d;

        if( ! estro.estasFinita()
            && x >= 0 && x < n && y >= 0 && y < n
            && (sxipoj[x][y] & PAF) == 0 ) {
            esploru( x, y );
            estro.gxiAgis();
        }
        return true;
    }
        

    /**
     * Esploru la efikon de pafo.
     * Se en la kampeto estas netrafita sxipo, gxi trafigxas;
     * se gxi estas komplete detruita, gxi sinkas.
     * Se estas maro, rezultas maltrafo.
     */
    protected void esploru( int x, int y ) {
        if( sxipoj[x][y] == SX ) {
            sxipoj[x][y] = TR;
            if( ! ioRestas( x, y ) ) {
                sinkigu( x, y );
            }
        }
        else {
            sxipoj[x][y] = MT;
        }
        repaint();
    }


    /**
     * testu, cxu la sxipo cxe (x,y) estas jam komplete trafita
     * @param x la horizontala koordinato
     * @param y la vertikala koordinato
     * @returns cxu restas netrafita parto de la sxipo
     */
    protected boolean ioRestas( int x, int y ) {
        if( x < 0 || x >= n ) return false;
        if( y < 0 || y >= n ) return false;
        if( sxipoj[x][y] == SX ) return true;
        if( sxipoj[x][y] == TR ) {
            sxipoj[x][y] = SI; // supozu momente ke gxi sinkis
            boolean f = ioRestas( x-1, y )
                     || ioRestas( x+1, y )
                     || ioRestas( x, y-1 )
                     || ioRestas( x, y+1 );
            sxipoj[x][y] = TR; // remetu la antauxan staton
            return f;
        }
        return false;
    }

    /**
     * komplete sinkigu la sxipon cxe (x,y), markante cxiujn
     * gxiajn partojn per "SI".
     * @param x la horizontala koordinato
     * @param y la vertikala koordinato
     */
    protected void sinkigu( int x, int y ) {
        if( x >= 0 && x < n && y >= 0 && y < n ) {
            if( sxipoj[x][y] == TR ) {
                sxipoj[x][y] = SI;
                sinkigu( x-1, y );
                sinkigu( x+1, y );
                sinkigu( x, y-1 );
                sinkigu( x, y+1 );
            }
        }
    }

    /**
     * Metu sxipon de grandeco gr.
     * @param gr la grandeco de la sxipo.
     */
    protected void metuSxipon( int gr ) {
        boolean sukceso = false;
        while(! sukceso ) {
            sukceso = provuMetiSxipon( gr );
            finuMetadon( sukceso );
        }
    }

    /**
     * Lasta pasxo en la metado ne nova sxipo.
     * Se la metado sukcesis, sxangxu la statojn de la koncernataj
     * kampoj jene:
     * <UL>
     * <LI>Kandidato (KA) farigxas apudsxipa kampo (AP)</LI>
     * <LI>Konstruato (SX0) farigxas sxipo(-parto) (SX)</LI>
     * <LI>Apudsxipa kampo (AP0) farigxas definitiva apudsxipa kampo (AP)</LI>
     * </UL>
     * Cxe malsukceso, cxio refarigxas maro.
     */
    protected void finuMetadon( boolean sukceso ) {
            for( int x = 0; x < n; x++ ) {
                for( int y = 0; y < n; y++ ) {
                    if( sxipoj[x][y] == KA )
                        sxipoj[x][y] = sukceso ? AP : MA;
                    if( sxipoj[x][y] == SX0 )
                        sxipoj[x][y] = sukceso ? SX : MA;
                    if( sxipoj[x][y] == AP0 )
                        sxipoj[x][y] = sukceso ? AP : MA;
                }
            }
    }

    /**
     * Provu, cxu eblas meti sxipon de grandeco <TT>gr</TT>.
     * Por tio unue hazarde difinu kampon kaj metu
     * gxiajn najbarojn en dumtempan staton,
     * kiu indikas, ke ili partoprenas en la metado de nova sxipo.
     * @return cxu sukcesis la metado
     */
    private boolean provuMetiSxipon( int gr ) {
        boolean sukceso = true;
        java.util.Vector najbaroj = new java.util.Vector(20);

        int x, y;
        do {
            x = (int) (Math.random( )*n) % n;
            y = (int) (Math.random( )*n) % n;
        } while( sxipoj[x][y] != MA );
        sxipoj[x][y] = SX0;
        memoruNajbaron( x-1, y,   KA );
        memoruNajbaron( x+1, y,   KA );
        memoruNajbaron( x, y-1,   KA );
        memoruNajbaron( x, y+1,   KA );
        memoruNajbaron( x-1, y-1, AP0 );
        memoruNajbaron( x+1, y-1, AP0 );
        memoruNajbaron( x-1, y+1, AP0 );
        memoruNajbaron( x+1, y+1, AP0 );

        while( --gr > 0 ) {
            // aldonu la reston de la sxipo:
            najbaroj.removeAllElements();
            for( int xx = 0; xx < n; xx++ ) {
                for( int yy = 0; yy < n; yy++ ) {
                    if( sxipoj[xx][yy] == KA )
                        najbaroj.addElement( new Integer( xx+n*yy ) );
                }
            }
            if( najbaroj.size() == 0 ) {
                sukceso = false;
                System.out.println("ne estas kandidatoj");
            }
            else {
                int h = haz( najbaroj.size() );
                x = ((Integer) najbaroj.elementAt( h )).intValue() % n;
                y = ((Integer) najbaroj.elementAt( h )).intValue() / n;
                sxipoj[x][y] = SX0;
            }
            memoruNajbaron( x-1, y,   KA );
            memoruNajbaron( x+1, y,   KA );
            memoruNajbaron( x, y-1,   KA );
            memoruNajbaron( x, y+1,   KA );
            memoruNajbaron( x-1, y-1, AP0 );
            memoruNajbaron( x+1, y-1, AP0 );
            memoruNajbaron( x-1, y+1, AP0 );
            memoruNajbaron( x+1, y+1, AP0 );
        }

        return sukceso;
    }

    /**
     * Metu ludkampeton en novan staton,
     * se gxi estas maro (MA), aux se gxi estas apud sxipkandidato
     * kaj nun mem farigxu kandidato.
     * Alie faru nenion.
     * @param x  horizontala koordinato de la kampeto
     * @param y  vertikala koordinato de la kampeto
     * @param kio  la nova stato por la kampeto
     */
    protected void memoruNajbaron( int x, int y, int kio ) {
        if( x >= 0 && x < n && y >= 0 && y < n ) {
            if( sxipoj[x][y] == MA ||
                sxipoj[x][y] == AP0 && kio == KA ) {
                sxipoj[x][y] = kio;
            }
        }
    }

    /**
     * @return cxu tiu cxi sxiparo estas venkita
     */
    public boolean venkita() {
        boolean v = kompleta;

        eksteraCiklo:
        for( int x= 0; x < n; x++ ) {
            for( int y= 0; y < n; y++ ) {
                if( sxipoj[x][y] == SX ) {
                    v = false;
                    break eksteraCiklo;
                }
            }
        }
        return v;
    }

    /**
     * @return hazardan nombron inter 0 kaj (n-1)
     */
    protected int haz( int n ) {
        return (int)( Math.random() * n ) % n;
    }

};

/**
 * "GxiaSxiparo" estas Sxiparo, kiun kunmetas la uzanto
 */
class GxiaSxiparo extends Sxiparo {
    int metendajKampoj = 0;
    boolean unuaKampo;
    Vector konstruendaj;
    int iKonstruenda = -1;

    /**
     * "GxiaSxiparo" estas konstruata same kiel "Sxiparo",
     * la diferenco estas en la metado de la sxipoj
     * @param n la longeco kaj largxeco de la "maro"
     */
    public GxiaSxiparo( int n, Sxiparestro estro ) {
        super( n, estro );
        kompleta = false;
        sxipojVideblaj = true; // gxi vidu siajn sxipojn
    }

    protected void metuSxipon( int gr ) {
        estro.mesagxu("Metu viajn sxipojn...");

        if( konstruendaj == null )
            konstruendaj = new Vector();
        if( metendajKampoj == 0 ) {
            metendajKampoj = gr;
            unuaKampo = true;
            iKonstruenda = 0;
        }
        else {
            konstruendaj.addElement( new Integer( gr ) );
        }
    }

    /**
     * La uzanto klakis per la muso (espereble) por meti sxipon.
     * Se ne plu estas sxipoj metendaj, faru nenion.
     * Alie (plu)konstruu novan sxipon, se la klako konformas
     * al la reguloj.
     */
    public boolean mouseDown( Event e, int xx, int yy ) {
        if( metendajKampoj > 0 ) {
            int x = xx / d;
            int y = yy / d;

            if( ! estro.estasFinita() &&
                (x >= 0 && x < n && y >= 0 && y < n ) &&
                (sxipoj[x][y] == MA && unuaKampo
                  || sxipoj[x][y] == KA ) ) {
                sxipoj[x][y] = SX0;
                memoruNajbaron( x-1, y,   KA );
                memoruNajbaron( x+1, y,   KA );
                memoruNajbaron( x, y-1,   KA );
                memoruNajbaron( x, y+1,   KA );
                memoruNajbaron( x-1, y-1, AP0 );
                memoruNajbaron( x+1, y-1, AP0 );
                memoruNajbaron( x-1, y+1, AP0 );
                memoruNajbaron( x+1, y+1, AP0 );

                metendajKampoj--;
                unuaKampo = false;
            }

            if( metendajKampoj == 0 ) { // lasta kampo de la sxipo
                finuMetadon( true );
                iKonstruenda++;
                if( iKonstruenda < konstruendaj.size() ) {
                    metendajKampoj = ((Integer)
                                      konstruendaj.elementAt(
                                         iKonstruenda )) .intValue();
                    unuaKampo = true;
                    Graphics g = getGraphics();
                    g.drawString( " "+metendajKampoj, n*d, 10 );
                    estro.mesagxu("Metu sxipon de grandeco " +
                                  metendajKampoj);
                }
                else {
                    metendajKampoj = 0;
                    Graphics g = getGraphics();
                    g.clearRect( n*d, 10, 10, 20 );
                    kompleta = true;
                    estro.mesagxu("Sxiparoj kompletaj.");
                }
            }
            else {   // restas kampoj por aldoni al tiu cxi sxipo
                int kandidatoj = 0;
                for( int x0 = 0; x0 < n; x0++ ) {
                    for( int y0 = 0; y0 < n; y0++ ) {
                        if( sxipoj[x0][y0] == KA )
                            kandidatoj ++;
                    }
                }
                if( kandidatoj == 0 ) {
                        // nuligu tiun cxi metadon kaj rekomencu:
                    System.out.println("ne restas ebla kandidato!");
                    finuMetadon( false );
                    metendajKampoj = ((Integer)
                                      konstruendaj.elementAt(
                                         iKonstruenda )) .intValue();
                    unuaKampo = true;             
                }
            }

            repaint();
        }

        return true;
    }

    /**
     * faru esploran "movon", t. e. testu unu malamikan kampon.
     * Uzu nur tiujn informojn, kiujn ni rajte posedas!
     */
    public void faruEsploron() {
        int x = 0, y = 0;
        boolean trovis = false;

        sercxuNekompletanSxipon:
        for( x = 0; x < n; x++ ) {
            for( y = 0; y < n; y++ ) {
                if( (sxipoj[x][y] & PAF) == 0 
                 && ( trovisCxe( x-1, y, SX )
                   || trovisCxe( x+1, y, SX )
                   || trovisCxe( x, y-1, SX )
                   || trovisCxe( x, y+1, SX ) ) ) {
                    trovis = true;
                    break sercxuNekompletanSxipon;
                }
            }
        }

        while(! trovis ) {
            x = haz( n );
            y = haz( n );
            trovis = true;
            if( ( sxipoj[x][y] & PAF) != 0 )
                trovis = false;  // tiun ni jam esploris
            if( trovisCxe( x-1, y, SI ) ) trovis = false;
            if( trovisCxe( x+1, y, SI ) ) trovis = false;
            if( trovisCxe( x, y-1, SI ) ) trovis = false;
            if( trovisCxe( x, y+1, SI ) ) trovis = false;
            if( trovisCxe( x-1, y-1, SI ) ) trovis = false;
            if( trovisCxe( x+1, y-1, SI ) ) trovis = false;
            if( trovisCxe( x-1, y+1, SI ) ) trovis = false;
            if( trovisCxe( x+1, y+1, SI ) ) trovis = false;
        }
        esploru( x, y );
    }

    /**
     * ekzamenu, cxu tie ni jam trovis certan objekton
     */
    private boolean trovisCxe( int x, int y, int ob ) {
        return
            ( x >= 0 && x < n && y >= 0 && y < n &&
                sxipoj[x][y] == (ob | PAF) );
    }    

};