/* Use the Java I/O routines */
import java.io.*;

/**
 * See BIO exam paper.  This program solves BIO'97 question 2
 * using strategy 2 to play Reversi.
 *
 * Example run using strategy 1:
 * <PRE>
 * .0*.
 * 0..0
 * 0000
 * 0*.0
 * 
 * Strategy 1
 * ........
 * ........
 * ...0*...
 * ..0..0..
 * ..0000..
 * ..0*.0..
 * ........
 * ........
 * 
 * 1
 * ........
 * ........
 * ...0*...
 * ..0..0..
 * ..0000..
 * ..00.0..
 * ....0...
 * ........
 * 
 * 0
 * 7 4
 * ........
 * ........
 * ...0*...
 * ..0..*..
 * ..0000*.
 * ..00.0..
 * ....0...
 * ........
 * 
 * 4
 * ........
 * .....*..
 * ...0**..
 * ..0*.*..
 * .**00**.
 * ..00.0..
 * ....0...
 * ........
 * 
 * 0
 * 1 4
 * ........
 * .....*..
 * ...0**..
 * ..0*.*..
 * 00000**.
 * ..00.0..
 * ....0...
 * ........
 * 
 * -1
 * </PRE>
 * (End of example for strategy 1.)
 *
 * Example run using strategy 2:
 * <PRE>
 * .0*.
 * 0..0
 * 0000
 * 0*.0
 * 
 * Strategy 2
 * ........
 * ........
 * ...0*...
 * ..0..0..
 * ..0000..
 * ..0*.0..
 * ........
 * ........
 * 
 * 
 * 99
 * ********
 * ******0*
 * **0***00
 * *000**00
 * *00*0000
 * *0*00000
 * **0**000
 * *****000
 * 
 * Black wins by 8.
 * </PRE>
 * (End of example for strategy 2.)
 *
 * Solution copyright (c) 1997 The British Informatics Olympiad (BIO).
 *
 * This program may be freely copied by persons or organisations
 * involved in the British Informatics Olympiad or the International
 * Olympiad in Informatics, on condition that no changes are made and
 * this notice is not altered. Distribution for profit is forbidden
 * unless permission is first obtained in writing from the BIO.
 *
 * This program is for educational purposes only and comes with no
 * warranty, implied or otherwise, as to its fitness for any purpose.
 *
 * Author:   Antony Rix
 * Internet: http://www.christs.cam.ac.uk/bio/
 * E-mail:   a.rix@lineone.net
 * S-mail:   The British Informatics Olympiad
 *           Christ's College
 *           Cambridge CB2 3BU
 *           United Kingdom
 */
class Reversi2 extends AppletConsoleApp {
  /**
   * This DataInputStream is used for parsing the input.
   */
  DataInput din;
   
  /**
   * Integer representing a blank square (0).
   */
  int blank = 0;

  /**
   * Integer representing a square with a white piece (1).
   */
  int white = 1;

  /**
   * Integer representing a square with a black piece (2).
   */
  int black = 2;

  /**
   * 3-element array giving the symbol for each square/piece.
   */
  char[] symbol = {'.', '0', '*'};

  /**
   * Current board.
   */
  int[][] currentBoard = new int[10][10];

  /**
   * Old board used to back up the current board when moves are made.
   */
  int[][] oldBoard = new int[10][10];

  /**
   * New board used to hold the player's prospective move.
   */
  int[][] newBoard = new int[10][10];

  /**
   * nWhite represents the number of white pieces on the board.
   *
   * nBlack represents the number of black pieces on the board.
   *
   * nPlayed represents the total number of pieces on the board.
   */
  int nWhite, nBlack, nPlayed;

  /**
   * The current player, equal to white (1) or black (2).
   */
  int player;
  
  /**
   * Start the application from the command line.
   */
  public static void main(String[] args) {
	  Reversi2 thisApp = new Reversi2();
	  thisApp.redirectStreams(System.in, System.out);
	  thisApp.run();
	}

  /**
   * Main program of Reversi2, this is run from the command line
   * by the <CODE>main()</CODE> method, or called directly by an
   * AppletConsole.
   *
   * The program reads from the stream <CODE>in</CODE> and writes
   * to the stream <CODE>out</CODE>, which are automatically assigned
   * by <CODE>main()</CODE> or by the AppletConsole class.
   */
	public void run() {
    din = new DataInputStream(in);
    initialiseBoards();
    try {
      out.println("BIO'97 Q2: Reversi");
      readBoard(currentBoard);
      out.println();
      out.println("Strategy 2");
      showBoard(currentBoard);
      play();
      out.println("Reversi finished.");
    }
    catch (IOException e) { out.println("I/O error!"); }
    catch (NumberFormatException e) { out.println("Invalid input format!"); }
  }
  
  /**
   * Initialise the boards to all blanks, including the area of 1
   * piece in width which is used to border the boards.
   */
  public void initialiseBoards() {
    int i, j;
    for( i = 0; i < 10; i++)
      for( j = 0; j < 10; j++) {
        currentBoard[i][j] = blank;
        oldBoard[i][j] = blank;
        newBoard[i][j] = blank;
      }
  }

  /**
   * Read a 4x4 Reversi centre board from the input.
   */
  public void readBoard(int[][] Board) throws IOException {
    int i, j;
    char c;
    out.println("Enter 4x4 board as follows:");
    out.println(" '.' represents blank");
    out.println(" '0' represents white");
    out.println(" '*' represents black.");
    for( i = 1; i <= 8; i++ )
      for( j = 1; j <= 8; j++ )
        Board[i][j] = blank;
    for( i = 6; i >= 3; i-- ) {
      for( j = 3; j <= 6; j++ ) {
        c = (char)din.readByte();
        switch (c) {
          case '.': Board[i][j] = blank; break;
          case '0': Board[i][j] = white; break;
          case '*': Board[i][j] = black; break;
          default:
            out.println("Invalid character '" + (int)c + "' taken as blank.");
            Board[i][j] = blank; break;
        }
      }
      c = (char)din.readByte();
      if( c == '\r')
        c = (char)din.readByte();
    }
  }

  /**
   * Copy one board onto another.
   */
  public void copyBoard(int[][] fromBoard, int[][] toBoard) {
    int i, j;
    for( i = 1; i <= 8; i++)
      for( j = 1; j <= 8; j++)
        toBoard[i][j] = fromBoard[i][j];
  }
  
  /**
   * Display a board on screen.
   */
  public void showBoard(int[][] Board) {
    int i, j;
    for( i = 8; i >= 1; i--) {
      for( j = 1; j <= 8; j++)
        out.print(symbol[Board[i][j]]);
      out.println();
    }
    out.println();
  }
  
  /**
   * Play the game.
   */
  public void play() throws IOException, NumberFormatException {
    int i, j;
    String cmd;
    int action;
    countPieces(currentBoard);
    player = white;

    action = 0;
    if (nPlayed < 64)
    do {
      cmd = din.readLine();
      action = Integer.parseInt(cmd);
      
      if (action > -1) {
        if (action == 0) {
          cmd = din.readLine();
          j = cmd.charAt(0) - (int)'0';
          i = cmd.charAt(2) - (int)'0';
          if ((i < 1) || (i > 8) || (j < 1) || (j > 8))
            out.println("Expected a location between (1,1) and (8,8)");
          else if (currentBoard[i][j] != blank) 
            out.println("That square is occupied!");
          else if (!hasNeighbour(currentBoard, i, j))
            out.println("That square has no neighbour");
          else {
            placePiece(currentBoard, player, i, j);
            showBoard(currentBoard);
            countPieces(currentBoard);
            player = enemyPlayer(player);
          }
        }
        else {
          while ((nPlayed < 64) && (action > 0)) {
            playBestMove2();
            countPieces(currentBoard);
            player = enemyPlayer(player);
            action--;
          }
          showBoard(currentBoard);
        }
      }
    } while ((nPlayed < 64) && (action >= 0));
    if (nPlayed == 64) {
      if (nWhite > nBlack)
        out.println("White wins by " + (nWhite - nBlack) + ".");
      else if (nWhite < nBlack)
        out.println("Black wins by " + (nBlack - nWhite) + ".");
      else
        out.println("Black and white draw.");
    }
  }

  /**
   * Counts the number of pieces of either colour in currentBoard
   * and sets nWhite etc. accordingly.
   */
  public void countPieces(int[][] Board) {
    nWhite = 0;
    nBlack = 0;
    int i, j;
    for( i = 1; i <= 8; i++)
      for( j = 1; j <= 8; j++)
        switch (Board[i][j]) {
          case 1: nWhite++; break;
          case 2: nBlack++; break;
        }
    nPlayed = nWhite + nBlack;
  }
  
  /**
   * Returns the player's opponent, or blank if the argument is not
   * a colour.
   */
  public int enemyPlayer(int Player) {
    if (Player == black)
      return white;
    else if (Player == white)
        return black;
    else
        return blank;
  }
  
  /**
   * Returns true if a square has at least one neighbouring piece
   * and is therefore available for a move.
   */
  public boolean hasNeighbour(int[][] Board, int i, int j) {
    if ((Board[i-1][j-1] + Board[i-1][j  ] + Board[i-1][j+1] + 
         Board[i  ][j-1] +                   Board[i  ][j+1] + 
         Board[i+1][j-1] + Board[i+1][j  ] + Board[i+1][j+1]) == blank)
      return false;
    else
      return true;
  }

  /**
   * Place a piece for player at (i, j) on Board.
   *
   * Returns the number of opposing pieces turned.
   */
  public int placePiece(int[][] Board, int player, int i, int j) {
    Board[i][j] = player;
    return makeSwap(Board, player, i, j, -1, -1) +
           makeSwap(Board, player, i, j, -1,  0) + 
           makeSwap(Board, player, i, j, -1,  1) + 
           makeSwap(Board, player, i, j,  0, -1) + 
           makeSwap(Board, player, i, j,  0, +1) + 
           makeSwap(Board, player, i, j,  1, -1) + 
           makeSwap(Board, player, i, j,  1,  0) + 
           makeSwap(Board, player, i, j,  1, +1);
  }
  
  /**
   * Returns true if a move at (i,j) would enable one or more
   * enemy pieces to be turned in direction (di,dj).
   */
  public boolean canSwap(int[][] Board, int player,
      int i, int j, int di, int dj) {
    int enemy = enemyPlayer(player);
    if (Board[i + di][j + dj] != enemy)
      return false;
    else {
      do {
        i = i + di;
        j = j + dj;
      } while (Board[i][j] == enemy);
      return (Board[i][j] == player);
    }
  }
    
  /**
   * Makes swaps on the board and returns the number of swaps made.
   */
  public int makeSwap(int[][] Board, int player,
      int i, int j, int di, int dj) {
    int enemy = enemyPlayer(player);
    boolean swapping = canSwap(Board, player, i, j, di, dj);
    int turned = 0;
    while (swapping) {
      i = i + di;
      j = j + dj;
      swapping = (Board[i][j] == enemy);
      if (swapping) {
        turned++;
        Board[i][j] = player;
      }
    }
    return turned;
  }

  /**
   * Plays the best move for the given player using strategy 2.
   */
  public void playBestMove2() {
    int enemy = enemyPlayer(player);
    int advantageBestPlayer = -999;
    int iBestPlayer = 0;
    int jBestPlayer = 0;
    int advantageBestEnemy;
    int iBestEnemy = 0;
    int jBestEnemy = 0;
    int advantagePlayer, advantageEnemy;
    int iPlayer, jPlayer;
    int iEnemy, jEnemy;
    
    if (nPlayed == 63) {
      // This is the algorithm for strategy 1, which we use as there
      // is only one go left.
      copyBoard(currentBoard, oldBoard);
      for( iPlayer = 1; iPlayer <= 8; iPlayer++ )
        for( jPlayer = 8; jPlayer >= 1; jPlayer-- )
          if ((currentBoard[iPlayer][jPlayer] == blank) &&
              (hasNeighbour(currentBoard, iPlayer, jPlayer))) {
            advantagePlayer =
              placePiece(currentBoard, player, iPlayer, jPlayer);
            
            if (advantagePlayer > advantageBestPlayer) {
              advantageBestPlayer = advantagePlayer;
              iBestPlayer = iPlayer;
              jBestPlayer = jPlayer;
            }
            copyBoard(oldBoard, currentBoard);
          }
    }
    else {
      // This is the algorithm for strategy 2.
      copyBoard(currentBoard, oldBoard);
      for( iPlayer = 1; iPlayer <= 8; iPlayer++ )
        for( jPlayer = 8; jPlayer >= 1; jPlayer-- )
          if ((currentBoard[iPlayer][jPlayer] == blank) &&
              (hasNeighbour(currentBoard, iPlayer, jPlayer))) {
            advantagePlayer =
              placePiece(currentBoard, player, iPlayer, jPlayer);
            
            advantageBestEnemy = -999;
            copyBoard(currentBoard, newBoard);
            for( iEnemy = 1; iEnemy <= 8; iEnemy++ )
              for( jEnemy = 1; jEnemy <= 8; jEnemy++ )
                if ((currentBoard[iEnemy][jEnemy] == blank) &&
                    (hasNeighbour(currentBoard, iEnemy, jEnemy))) {
                  advantageEnemy =
                    placePiece(currentBoard, enemy, iEnemy, jEnemy);
                  if (advantageEnemy > advantageBestEnemy) {
                    advantageBestEnemy = advantageEnemy;
                    iBestEnemy = iEnemy;
                    jBestEnemy = jEnemy;
                  }
                  copyBoard(newBoard, currentBoard);
                }
            if ((advantagePlayer - advantageBestEnemy) >
                 advantageBestPlayer) {
              advantageBestPlayer = advantagePlayer - advantageBestEnemy;
              iBestPlayer = iPlayer;
              jBestPlayer = jPlayer;
            }
            copyBoard(oldBoard, currentBoard);
          }
    }
    placePiece(currentBoard, player, iBestPlayer, jBestPlayer);
  }
}