import java.util.*;

import dibo.distanz.DistanzSpieler;
import dibo.distanz.DistanzSpielzug;

//-----------------------------------------------------
// Klasse DistanzDibo0
//-----------------------------------------------------
final public class DistanzProgramm
  extends DistanzSpieler 
{
 
// Attribute

  private DistanzBrett brett;
  private Random random = new Random(4711);

// Methoden

  // Initialisierungsmethode
  public void init(boolean weissOderSchwarz) {
    super.init(weissOderSchwarz);
    this.brett = new DistanzBrett();
  }

  // erfragt und liefert naechsten Spielzug des
  // Spielers; uebergeben wird der letzte Zug des
  // Gegners
  public DistanzSpielzug liefereNaechstenSpielzug (DistanzSpielzug gegnerZug) 
  {
    if (gegnerZug != null) { // nur wenn nicht der Anfangszug
      this.brett.fuehreSpielzugAus(gegnerZug);
    }
    DistanzSpielzug zug = this.ermittleSpielzug(this.brett);
    this.brett.fuehreSpielzugAus(zug);
    return zug;
  }
    
  // ermittelt neuen Spielzug
  private DistanzSpielzug ermittleSpielzug(DistanzBrett brett) {
    Vector zuege = findeLegaleZuege(brett);
 
    if ((zuege == null) || (zuege.size() == 0)) { // eigentlich nicht moeglich!
      System.err.println("ERROR: kein legaler Zug mehr moeglich!");
      return null;
    }
 
    // liefere einen Zug (random)
    
    return (DistanzSpielzug)zuege.elementAt(abs(this.random.nextInt()) % zuege.size());
  }

  private Vector findeLegaleZuege(DistanzBrett b) {
    Vector zuege = new Vector(10);
    for (int z=0; z<DistanzBrett.GROESSE; z++) {
      for (int s=0; s<DistanzBrett.GROESSE; s++) {
        DistanzFeld feld = b.liefereFeld(z, s);
        if (feld != null &&
            !feld.istLeer() &&
            feld.liefereFigur().istWeiss() == this.istWeiss()
           ) {
          for (int z2=0; z2<DistanzBrett.GROESSE; z2++) {
            for (int s2=0; s2<DistanzBrett.GROESSE; s2++) {
              DistanzSpielzug zug = 
                new DistanzSpielzug(z, s, z2, s2);
              if (DistanzRegeln.spielzugOK(b, zug, this.istWeiss())) {
                zuege.addElement(zug);
              }
            }
          }
        }
      }
    }
    return zuege;
  }

  // berechnet den Betrag einer Zahl
  static int abs(int zahl) {
    return zahl >= 0 ? zahl : -zahl;
  }

}   
 
//-----------------------------------------------------
// Klasse DistanzBrett
//-----------------------------------------------------
final class DistanzBrett {

/*
gewaehlte Datenstruktur:

   0 1 2 3 4 5 6 7
  +-+-+-+-+-+-+-+-+
0 | |h|k| |h|h| | |
  +-+-+-+-+-+-+-+-+
1 | | | | | | | | |
  +-+-+-+-+-+-+-+-+
2 | | | | | | | | |
  +-+-+-+-+-+-+-+-+
3 | | | | | | | | |
  +-+-+-+-+-+-+-+-+
4 | | | | | | | | |
  +-+-+-+-+-+-+-+-+
5 | | | | | | | | |
  +-+-+-+-+-+-+-+-+
6 | | | | | | | | |
  +-+-+-+-+-+-+-+-+
7 | | |H|H| |K|H| |
  +-+-+-+-+-+-+-+-+

repraesentiert als 8 x 8 - Matrix; 
Schwarze Spielfiguren:
  h = Helfer
  k = Koenig
  g = Gefangener

Weisse Spielfiguren:
  H = Helfer
  K = Koenig
  G = Gefangener
*/

// Konstanten
  final static int GROESSE = 8;
  final static int HELFER  = 3;

  final static int UNENDLICH = 1000000;

// Attribute
  DistanzFeld[][] brett;

// Methoden 
  // Konstruktor (Initialisierung des Distanz-Brettes)
  DistanzBrett() { 
    this.brett = new DistanzFeld[GROESSE][GROESSE];
    for (int z=0; z<GROESSE; z++) 
      for (int s=0; s<GROESSE; s++) 
        this.brett[z][s] = new DistanzFeld(z, s);

    // mit schwarzen Figuren besetzte Felder
    this.brett[0][1] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.SCHWARZ, 
                       DistanzFigur.HELFER_SCHWARZ), 0, 1);

    this.brett[0][2] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.SCHWARZ, 
                       DistanzFigur.KOENIG_SCHWARZ), 0, 2);

    this.brett[0][4] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.SCHWARZ, 
                       DistanzFigur.HELFER_SCHWARZ), 0, 4);

    this.brett[0][5] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.SCHWARZ, 
                       DistanzFigur.HELFER_SCHWARZ), 0, 5);

    // mit weissen Figuren besetzte Felder
    this.brett[GROESSE-1][2] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.WEISS, 
                       DistanzFigur.HELFER_WEISS), GROESSE-1, 2);

    this.brett[GROESSE-1][3] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.WEISS, 
                       DistanzFigur.HELFER_WEISS), GROESSE-1, 3);

    this.brett[GROESSE-1][5] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.WEISS, 
                       DistanzFigur.KOENIG_WEISS), GROESSE-1, 5);

    this.brett[GROESSE-1][6] = new DistanzFeld(
      new DistanzFigur(DistanzFigur.WEISS, 
                       DistanzFigur.HELFER_WEISS), GROESSE-1, 6);

  } 

  // Copy-Konstruktor
  DistanzBrett(DistanzBrett old) { 
    this.brett = new DistanzFeld[GROESSE][GROESSE];
    for (int z=0; z<GROESSE; z++) {
      for (int s=0; s<GROESSE; s++) {
        this.brett[z][s] = new DistanzFeld(old.brett[z][s]);
      }
    }
  }

  // Ausfuehrung eines Spielzugs auf dem Brett
  void fuehreSpielzugAus(DistanzSpielzug zug) { 
    int vonZeile = zug.vonWelcherZeile();
    int vonSpalte = zug.vonWelcherSpalte();
    int nachZeile = zug.inWelcheZeile();
    int nachSpalte = zug.inWelcheSpalte();

    DistanzFigur vonFigur = this.brett[vonZeile][vonSpalte].liefereFigur();
    DistanzFigur nachFigur = this.brett[nachZeile][nachSpalte].liefereFigur();

    if (this.brett[nachZeile][nachSpalte].istLeer()) { // leeres Feld
      this.brett[vonZeile][vonSpalte].entferneFigur();
      this.brett[nachZeile][nachSpalte].setzeFigur(vonFigur);
      return;
    } 

    // Figurentausch
    this.brett[vonZeile][vonSpalte].entferneFigur();
    this.brett[nachZeile][nachSpalte].entferneFigur();
    this.brett[nachZeile][nachSpalte].setzeFigur(vonFigur);
    this.brett[vonZeile][vonSpalte].setzeFigur(nachFigur);

    if (vonFigur.istWeiss() && nachFigur.istWeiss() ||
         !vonFigur.istWeiss() && !nachFigur.istWeiss()) { // Befreiung
      if (vonFigur.istKoenig()) {
        nachFigur.befreiung();
      }
    } else { // Gefangennahme
      nachFigur.gefangennahme();  // egal, wenn schon gefangen war
    }
      
  } 

  // Ausgabe des aktuellen Spielbretts
  void gebeSpielbrettAus() { 

    System.out.println();   
    System.out.println("  Spieler B (Schwarz)");
    System.out.println();   
    System.out.print("  ");
    for (int j=0; j<GROESSE; j++) {
      System.out.print(j); System.out.print(" ");
    }
    System.out.println();

    System.out.print("-");
    for (int j=0; j<GROESSE; j++)
      System.out.print("--");
    System.out.println();   

    for (int i=0; i<GROESSE; i++) {
      System.out.print(i);  
      System.out.print("|");
      for (int j=0; j<GROESSE; j++) {
        System.out.print(liefereZeichen(i, j));
        System.out.print("|");
      }  
      System.out.println();

      System.out.print("-");
      for (int j=0; j<GROESSE; j++)
        System.out.print("--");
      System.out.println();
    }
    System.out.println();
    System.out.println("  Spieler A (WEISS)");
    System.out.println();

  }

  // Lieferung der Figur an der Stelle pos
  DistanzFeld liefereFeld(Position pos) { 
    return this.brett[pos.liefereZeile()][pos.liefereSpalte()];
  }

  // Lieferung der Figur an der Stelle z/s
  DistanzFeld liefereFeld(int z, int s) { 
    return this.brett[z][s];
  }

  // Lieferung des Figurzeichens oder Leerzeichen, falls 
  // leeres Feld
  char liefereZeichen(int z, int s) { 
    if (this.brett[z][s].istLeer()) {
     return ' ';
    } else {
     return this.brett[z][s].liefereFigur().liefereTyp();
    }
  }

  // liefert alle Figuren eines Spielers
  DistanzFigur[] liefereFiguren(DistanzSpieler spieler) { 
    DistanzFigur[] figuren = new DistanzFigur[HELFER+1];
    int pos = 0;
    for (int z=0; z<GROESSE; z++) {
      for (int s=0; s<GROESSE; s++) {
        if (!this.brett[z][s].istLeer() &&
            this.brett[z][s].liefereFigur().istWeiss() ==
            spieler.istWeiss()) {
          figuren[pos++] = this.brett[z][s].liefereFigur();
        }
      }
    }
    return figuren;
  }

  // liefert alle Figuren eines Spielers
  DistanzFigur[] liefereFiguren(boolean istWeiss) { 
    DistanzFigur[] figuren = new DistanzFigur[HELFER+1];
    int pos = 0;
    for (int z=0; z<GROESSE; z++) {
      for (int s=0; s<GROESSE; s++) {
        if (!this.brett[z][s].istLeer() &&
            this.brett[z][s].liefereFigur().istWeiss() ==
            istWeiss) {
          figuren[pos++] = this.brett[z][s].liefereFigur();
        }
      }
    }
    return figuren;
  }

  // liefert Anzahl Gefangene
  int anzahlGefangene(DistanzFigur[] figuren) { 
    int anzahl = 0;
    for (int i=0; i<figuren.length; i++) {
      if (figuren[i].istGefangen()) anzahl++;
    }
    return anzahl;
  }

  // Koenig gefangen
  boolean koenigGefangen(DistanzFigur[] figuren) { 
    for (int i=0; i<figuren.length; i++) {
      if (figuren[i].istKoenig() && figuren[i].istGefangen()) return true;
    }
    return false;
  }

  // STELLUNGSBEWERTER
  int bewerteStellung() {
    DistanzFigur[] fWeiss = liefereFiguren(DistanzFigur.WEISS);
    DistanzFigur[] fSchwarz = liefereFiguren(DistanzFigur.SCHWARZ);

    if (koenigGefangen(fSchwarz)) return UNENDLICH;
    if (koenigGefangen(fWeiss)) return -UNENDLICH;

    int anzWeiss = anzahlGefangene(fWeiss);
    int anzSchwarz = anzahlGefangene(fSchwarz);
    return anzSchwarz - anzWeiss;
  }

}


//-----------------------------------------------------
// Klasse DistanzFeld
//-----------------------------------------------------
final class DistanzFeld {

  int zeile, spalte;
  DistanzFigur figur;

  DistanzFeld(int zeile, int spalte) {
    // leeres Feld
    this.figur = null;
    this.zeile = zeile;
    this.spalte = spalte;
  }

  DistanzFeld(DistanzFigur figur, int zeile, int spalte) {
    this.figur = figur;
    this.zeile = zeile;
    this.spalte = spalte;
    this.figur.neuesFeld(this);
  }

  DistanzFeld(DistanzFeld old) {
    if (old.figur == null) {
      this.figur = null;
    } else {
      this.figur = new DistanzFigur(old.figur);
      this.figur.neuesFeld(this);
    }
    this.zeile = old.zeile;
    this.spalte = old.spalte;
  }

  DistanzFigur liefereFigur() {
    return this.figur;
  }

  int liefereZeile() {
    return this.zeile;
  }

  int liefereSpalte() {
    return this.spalte;
  }

  boolean istLeer() {
    return this.figur == null;
  }

  DistanzFigur entferneFigur() {
    DistanzFigur fig = this.figur;
    this.figur = null;
    return fig;
  }

  void setzeFigur(DistanzFigur figur) {
    this.figur = figur;
    figur.neuesFeld(this);
  }

}

//-----------------------------------------------------
// Klasse DistanzFigur
//-----------------------------------------------------
final class DistanzFigur {

// Konstanten
  final static boolean WEISS   = true;
  final static boolean SCHWARZ = !WEISS;

  final static char HELFER_WEISS     = 'H';
  final static char KOENIG_WEISS     = 'K';
  final static char GEFANGENER_WEISS = 'G';

  final static char HELFER_SCHWARZ     = 'h';
  final static char KOENIG_SCHWARZ     = 'k';
  final static char GEFANGENER_SCHWARZ = 'g';


// Attribute
  boolean istWeiss;
  char typ;
  DistanzFeld feld;    
  boolean istGefangen;

// Methoden
  // Konstruktor (Initialisierung einer Figur)
  DistanzFigur(boolean istWeiss,
                      char typ
                     ) 
  {
    this.istWeiss = istWeiss; 
    this.typ = typ; 
    this.istGefangen = false;
    // anschliessend wird direkt neuesFeld aufgerufen und damit this.feld 
    //   initialisiert
  }

  DistanzFigur(DistanzFigur old) 
  {
    this.istWeiss = old.istWeiss; 
    this.typ = old.typ; 
    this.istGefangen = old.istGefangen;
    // anschliessend wird direkt neuesFeld aufgerufen und damit this.feld 
    //   initialisiert
  }

  boolean istWeiss() { 
    return this.istWeiss; 
  }

  int liefereZeile() { 
    return this.feld.liefereZeile(); 
  }

  int liefereSpalte() { 
    return this.feld.liefereSpalte(); 
  }

  char liefereTyp() { 
    if (!this.istGefangen) {
      return this.typ; 
    } else {
      if (this.istWeiss) return GEFANGENER_WEISS;
      return GEFANGENER_SCHWARZ;
    }
  }

  DistanzFeld liefereFeld() { 
    return this.feld; 
  }

  void neuesFeld(DistanzFeld feld) { 
    this.feld = feld; 
  }

  boolean istGefangen() { 
    return this.istGefangen; 
  }

  boolean istKoenig() { 
    return this.typ == KOENIG_SCHWARZ || this.typ == KOENIG_WEISS; 
  }

  boolean istHelfer() { 
    return this.typ == HELFER_SCHWARZ || this.typ == HELFER_WEISS; 
  }

  void gefangennahme() { 
    this.istGefangen = true; 
  }

  void befreiung() { 
    this.istGefangen = false; 
  }


}


//-----------------------------------------------------
// Klasse Position
//-----------------------------------------------------

final class Position {

// Attribute
  int zeile;
  int spalte;

// Methoden
  // Konstruktor (Initialisierung)
  Position(int z, int s) {
    this.zeile = z;
    this.spalte = s;
  }

  int liefereZeile() {
    return this.zeile;
  }

  int liefereSpalte() {
    return this.spalte;
  }

  boolean identisch(Position andere) {
    return this.zeile == andere.zeile && this.spalte == andere.spalte;
  }

  public String toString() {
    return this.zeile + "/" + this.spalte;
  }

}

//-----------------------------------------------------
// Klasse DistanzRegeln
//-----------------------------------------------------
final class DistanzRegeln {

// Methoden

  // Ueberpruefung eines Spielzugs
  static boolean spielzugOK(DistanzBrett brett,
                            DistanzSpielzug zug, 
                            boolean istWeiss
                           ) 
  {
    // korrekte Felder?
    if (zug.vonWelcherZeile() < 0 || 
        zug.vonWelcherSpalte() < 0 ||
        zug.vonWelcherZeile() >= DistanzBrett.GROESSE || 
        zug.vonWelcherSpalte() >= DistanzBrett.GROESSE ||
        zug.inWelcheZeile() < 0 || 
        zug.inWelcheSpalte() < 0 ||
        zug.inWelcheZeile() >= DistanzBrett.GROESSE || 
        zug.inWelcheSpalte() >= DistanzBrett.GROESSE) {
      return false;
    }

    // Figur darf nicht stehenbleiben !
    if (zug.vonWelcherZeile() == zug.inWelcheZeile() &&
        zug.vonWelcherSpalte() == zug.inWelcheSpalte()
       ) {
      return false;
    }

    // steht auf dem angegebenen Feld eine korrekte Figur ?
    DistanzFeld vonFeld = brett.liefereFeld(zug.vonWelcherZeile(), zug.vonWelcherSpalte());
    if (vonFeld.istLeer() ||
        (istWeiss != vonFeld.liefereFigur().istWeiss())
       ) {
      return false;
    }

    // Gefangene koennen nicht verschoben werden
    if (vonFeld.liefereFigur().istGefangen()) {
      return false;
    }

    // stimmt die Distanz ?
    int zeilenDistanz = abs(zug.vonWelcherZeile() - 
                            zug.inWelcheZeile());
    int spaltenDistanz = abs(zug.vonWelcherSpalte() - 
                             zug.inWelcheSpalte());
    DistanzFigur[] figuren = brett.liefereFiguren(istWeiss);
    boolean distanzOk = false;
    distanzUeberpruefung:
    for (int erste=0; erste<figuren.length; erste++) {
      for (int zweite=erste+1; zweite<figuren.length; zweite++) {
        if (figuren[erste] != brett.liefereFeld(zug.vonWelcherZeile(), zug.vonWelcherSpalte()).liefereFigur() &&
            figuren[zweite] != brett.liefereFeld(zug.vonWelcherZeile(), zug.vonWelcherSpalte()).liefereFigur()) {
          int zD = abs(figuren[erste].liefereFeld().liefereZeile() -
                       figuren[zweite].liefereFeld().liefereZeile());
          int sD = abs(figuren[erste].liefereFeld().liefereSpalte() -
                       figuren[zweite].liefereFeld().liefereSpalte());
          if (zeilenDistanz == zD && spaltenDistanz == sD ||
              zeilenDistanz == sD && spaltenDistanz == zD
             ) {
            distanzOk = true;
            break distanzUeberpruefung;
          }
        }
      }
    }
    if (!distanzOk) {
      return false;
    }

    // alles ok!
    return true;
  }

  // berechnet den Betrag einer Zahl
  static int abs(int zahl) {
    return zahl >= 0 ? zahl : -zahl;
  }

}