import java.io.*;

//-----------------------------------------------------
// Klasse TicTacToe-Spiel (TTTSpiel) / Hauptprogramm
//-----------------------------------------------------
public class TTTSpiel {

// Attribute
  protected TTTSpieler spieler_a, spieler_b;
  protected TTTBrett brett;
  protected TTTRegeln regeln;

// Methoden
 
  // Konstruktor (Initialisierung eines Spiels)
  public TTTSpiel(TTTSpieler a, TTTSpieler b, 
                  TTTBrett brett, TTTRegeln regeln) {
    this.spieler_a = a; this.spieler_b = b;
    this.brett = brett; this.regeln = regeln;
  }

  // Durchfuehrung eines Spiels
  public void spielen() {
    // Spieler A beginnt
    TTTSpieler akt_spieler = this.spieler_a;
    TTTSpielzug zug = null;
    this.brett.gebeSpielbrettAus();
 
 
    // abwechselndes Ziehen bis Spielende erreicht ist
    do {
      if (akt_spieler == this.spieler_a) 
        System.out.println("Spieler A ist am Zug!");
      else 
        System.out.println("Spieler B ist am Zug!");

      // legalen Spielzug ermitteln und ausfuehren
      zug = akt_spieler.liefereNaechstenSpielzug(zug);
      while (!this.regeln.spielzugOK(zug))
      {
        System.out.println("Ungueltig; neue Eingabe!");
        zug=akt_spieler.liefereNaechstenSpielzug(zug);
      }
      this.brett.fuehreSpielzugAus(akt_spieler, zug);
      this.brett.gebeSpielbrettAus();
 
      // der andere Spieler ist nun ab Zug
      if (akt_spieler == spieler_a)
        akt_spieler = this.spieler_b;
      else
        akt_spieler = this.spieler_a;
    } while (!this.regeln.spielEnde());
 
    // Spiel ist zuende
    this.regeln.gebeSiegerBekannt();
  }

  // Hauptprogramm; 
  // hier startet das TicTacToe-Programm
  public static void main(String[] args) {
    TTTSpieler a = 
      new TTTSpieler(TTTFigur.A_FIGUR);
    TTTSpieler b = 
      new TTTProgramm(TTTFigur.B_FIGUR, a);
    TTTBrett brett = new TTTBrett();
    TTTRegeln regeln = new TTTRegeln(brett);

    TTTSpiel tictactoe=new TTTSpiel(a,b,brett,regeln);
    tictactoe.spielen();
  }
}

//-----------------------------------------------------
// Klasse TicTacToe-Brett (TTTBrett)
//-----------------------------------------------------
class TTTBrett {

// Attribute
  protected TTTFigur[][] brett;

// Methoden 
  // Konstruktor (Initialisierung des TTT-Brettes)
  public TTTBrett() { 
    // anfangs ist das Spielbrett (3x3-Matrix) leer
    this.brett = new TTTFigur[3][3];
    for (int i=0; i<3; i++) 
      for (int j=0; j<3; j++) 
        this.brett[i][j] = null;
   } 

  // Ausfuehrung eines Spielzugs auf dem Brett
  public void fuehreSpielzugAus(TTTSpieler spieler, 
                                TTTSpielzug zug) { 
    // abhaengig vom aktuellen Spieler, wird eine 
    // A_Figur oder eine B_Figur an die Stelle 
    //  gesetzt, die der Spielzug angibt
    int z = zug.welcheZeile();
    int s = zug.welcheSpalte();
    if (spieler.istSpielerA()) 
      this.brett[z][s] = 
        new TTTFigur(TTTFigur.A_FIGUR, z, s, this);
    else 
      this.brett[z][s] = 
        new TTTFigur(TTTFigur.B_FIGUR, z, s, this);
  } 

  // Ausgabe des aktuellen Spielbretts
  public void gebeSpielbrettAus() { 
    System.out.print("  ");
    for (int j=0; j<3; j++) {
      System.out.print(j); System.out.print(" ");
    }
    System.out.println();

    System.out.print("-");
    for (int j=0; j<3; j++) 
      System.out.print("--");
    System.out.println();
 
    for (int i=0; i<3; i++) {
      System.out.print(i);
      System.out.print("|");
      for (int j=0; j<3; j++) {
        if (this.brett[i][j] == null)
          System.out.print(" ");
        else if (this.brett[i][j].istAFigur()) 
          System.out.print("X");
        else 
          System.out.print("O");
        System.out.print("|");
      }  
      System.out.println();
 
      System.out.print("-");
      for (int j=0; j<3; j++) 
        System.out.print("--");
      System.out.println();
  } }


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

//-----------------------------------------------------
// Klasse TicTacToe-Figur (TTTFigur)
//-----------------------------------------------------
class TTTFigur {

// Konstanten
  public final static boolean A_FIGUR = true;
  public final static boolean B_FIGUR = !A_FIGUR;

// Attribute
  protected boolean a_oder_b;  // a == true
  protected int zeile;         // 0 - 2
  protected int spalte;        // 0 - 2
  protected TTTBrett brett;

// Methoden
  // Konstruktor (Initialisierung einer Figur)
  public TTTFigur(boolean a_oder_b,
                  int zeile, int spalte,
                  TTTBrett brett) {
    this.a_oder_b = a_oder_b; this.brett = brett;
    this.zeile = zeile; this.spalte = spalte;
  }

  public boolean istAFigur() { return this.a_oder_b; }
  public int welcheZeile() { return this.zeile; }
  public int welcheSpalte() { return this.spalte; }

}

//-----------------------------------------------------
// Klasse TicTacToe-Spielzug (TTTSpielzug)
//-----------------------------------------------------
class TTTSpielzug {

// Attribute
  protected int zeile;  // 0 - 2
  protected int spalte; // 0 - 2
 
// Methoden
  // Konstruktor (Initialisierung eines Spielzugs)
  public TTTSpielzug(int z, int s) {
    this.zeile = z; this.spalte = s;
  }
  public int welcheZeile() { return this.zeile; }
  public int welcheSpalte() { return this.spalte; }
}
 
//-----------------------------------------------------
// Klasse TicTacToe-Regeln (TTTRegeln)
//-----------------------------------------------------
class TTTRegeln {

// Attribute
  protected TTTBrett brett;

// Methoden
  // Konstruktor (Initialisierung der Regeln)
  public TTTRegeln(TTTBrett brett) {
    this.brett = brett;
  }

  // Ueberpruefung eines Spielzugs
  public boolean spielzugOK(TTTSpielzug zug) {
    // ein Spielzug ist ok, wenn die Positionangaben 
    // im gueltigen Bereich liegen und noch keine 
    // Figur auf dem angegeben Feld existiert
    return
      (zug.welcheZeile() >= 0) && 
      (zug.welcheZeile() <= 2) &&
      (zug.welcheSpalte() >= 0) && 
      (zug.welcheSpalte() <= 2) &&
      (this.brett.liefereFigur(zug.welcheZeile(), 
            zug.welcheSpalte()) == null);
  }

  // Ueberpruefung des Spielendes
  public boolean spielEnde() {
    // ein Spiel st beendet, wenn alle Felder 
    // besetzt sind oder wenn ein Sieger feststeht
    int besetzte_felder = 0;
    for (int i=0; i<3; i++) 
      for (int j=0; j<3; j++) 
        if (this.brett.liefereFigur(i, j) != null) 
          besetzte_felder++;
    return (besetzte_felder == 9) || 
           (this.ermittleSieger() != ' ');
  }

  // Ausgabe des Siegers
  public void gebeSiegerBekannt() {
    char sieger = this.ermittleSieger();
    if (sieger == 'A') 
      System.out.println("Sieger ist Spieler A!");
    else if (sieger == 'B') 
      System.out.println("Sieger ist Spieler B!");
    else 
      System.out.println("Unentschieden!");
  }

  // Ermittlung des Siegers
  private char ermittleSieger() {
    // es existieren acht Alternativen, die getestet 
    // werden muessen
    char sieger = ' ';
    if ((sieger=this.testeReihe(0,0,0,1,0,2))!=' ')
      return sieger;
    if ((sieger=this.testeReihe(1,0,1,1,1,2))!=' ')
      return sieger;
    if ((sieger=this.testeReihe(2,0,2,1,2,2))!=' ')
      return sieger;
    if ((sieger=this.testeReihe(0,0,1,0,2,0))!=' ')
      return sieger;
    if ((sieger=this.testeReihe(0,1,1,1,2,1))!=' ')
      return sieger;
    if ((sieger=this.testeReihe(0,2,1,2,2,2))!=' ')
      return sieger;
    if ((sieger=this.testeReihe(0,0,1,1,2,2))!=' ')
      return sieger;
    if ((sieger=this.testeReihe(0,2,1,1,2,0))!=' ')
      return sieger;
    return ' '; // noch kein Sieger
  }

  // Ueberpruefung einer Reihe
  private char testeReihe(int z1, int s1, 
                          int z2, int s2,
                          int z3, int s3) {
    if ((this.brett.liefereFigur(z1,s1) != null) &&
        (this.brett.liefereFigur(z2,s2) != null) &&
        (this.brett.liefereFigur(z3,s3) != null) &&
        (this.brett.liefereFigur(z1,s1).istAFigur() ==
          this.brett.liefereFigur(z2,s2).istAFigur()) 
        &&
        (this.brett.liefereFigur(z1,s1).istAFigur() ==
          this.brett.liefereFigur(z3,s3).istAFigur())
       ) {
      if (this.brett.liefereFigur(z1,s1).istAFigur()) 
        return 'A'; // Spieler A ist Sieger
      else 
        return 'B'; // Spieler B ist Sieger
    }
    return ' '; // noch kein Sieger
  }
}


//-----------------------------------------------------
// Klasse TicTacToe-Spieler (TTTSpieler)
//-----------------------------------------------------

class TTTSpieler {

// Attribute
  protected boolean ist_spieler_a;

// Methoden 
  // Konstruktor (Initialisierung eines Spielers)
  public TTTSpieler(boolean a_oder_b) {
    this.ist_spieler_a = a_oder_b;
  }

  // Ueberpruefung, ob es Spieler A ist
  public boolean istSpielerA() { 
    return this.ist_spieler_a; 
  }

  // erfragt und liefert naechsten Spielzug des 
  // Spielers; uebergeben wird der letzte Zug des
  // Gegners
  public TTTSpielzug 
   liefereNaechstenSpielzug (TTTSpielzug gegner_zug) { 
    return this.erfrageNaechstenSpielzugBeimSpieler(); 
  } 
 
  // erfragt naechsten Spielzug beim Spieler
  protected 
   TTTSpielzug erfrageNaechstenSpielzugBeimSpieler() {
    System.out.println("Zeile eingeben (0-2): ");
    int zeile = this.readInt();
    System.out.println("Spalte eingeben (0-2): ");
    int spalte = this.readInt();
    return new TTTSpielzug(zeile, spalte);
  }

  // Zahl einlesen
  private static int readInt() {
    DataInputStream input = 
      new DataInputStream(System.in);
    try {
      String eingabe = input.readLine();
      Integer i = new Integer(eingabe);
      return i.intValue();
   } catch (Exception e) { return -1; }
  }
}

//-----------------------------------------------------
// Klasse TicTacToe-Programm (TTTProgramm)
//-----------------------------------------------------
class TTTProgramm extends TTTSpieler {

// Attribute
  protected TTTBrett brett;
  protected TTTRegeln regeln;
  protected TTTSpieler gegner;

// Methoden 
  public TTTProgramm(boolean a_oder_b, 
                     TTTSpieler gegner) {
    super(a_oder_b);
    this.gegner = gegner;
    // auf einem eigenen Brett werden die Zuege
    // nachgehalten
    this.brett = new TTTBrett();
    this.regeln = new TTTRegeln(this.brett);
  }

  // Mitteilung, wer der Gegner ist
  public void setzeGegner(TTTSpieler gegner) {
    this.gegner = gegner; 
  } 

  // erfragt und liefert naechsten Spielzug des 
  // Spielers
  public TTTSpielzug
   liefereNaechstenSpielzug(TTTSpielzug gegner_zug) { 
    // zunaechst wird der gegnerische Zug auf dem 
    // eigenen Spielbrett nachgehalten
    if (gegner_zug != null) 
      this.brett.
        fuehreSpielzugAus(this.gegner, gegner_zug);
    // dann wird der eigene Zug berechnet, ebenfalls
    // nach gehalten und zurueckgeliefert
    TTTSpielzug eigener_zug = 
      this.ermittleNaechstenSpielzug();
    this.brett.fuehreSpielzugAus(this, eigener_zug);
    return eigener_zug;
  } 
 
  protected 
   TTTSpielzug ermittleNaechstenSpielzug() {
    // eine sehr einfache Strategie: 
    // das Programm waehlt das naechste freie Feld aus
    for (int i=0; i<3; i++) {
      for (int j=0; j<3; j++) {
        TTTSpielzug zug = new TTTSpielzug(i, j);
        if (regeln.spielzugOK(zug)) 
          return zug;
      }
    }
    return null;
  }
}