/********************************************************************* Problem: Petteia Competition: American Computer Science League #3 Section: Senior Author: Teacher Gerry Donaldson Date of Competition: March 2008 Programming Language: Java Development Environment: Eclipse 3.3 System: Intel Celeron 3 Ghz, Windows XP School Number: 080601825 School: Sir Winston Churchill High School, Calgary, Alberta, Canada *********************************************************************/ import java.io.BufferedReader; import java.io.FileReader; import java.io.IOException; import java.util.StringTokenizer; public class Petteia { static private int row = 0, col = 0; static private char marker = '\0'; static private char[][] captured = new char[ 10 ][ 10 ]; static private int[][] coord; static private String cap = "", blk = ""; static public void main( String[] args ) throws IOException { char[][] grid = initializeGrid(); int numOfLocations = grabData(); for( int i = 0; i < numOfLocations; i++ ) { marker = i % 2 == 0 ? 'o' : 'x'; grid = addMarker( grid, i ); checkCaptured( grid ); } // end for grid = initializeGrid(); for( int i = 0; i < numOfLocations; i++ ) { marker = i % 2 == 0 ? 'o' : 'x'; grid = addMarker( grid, i ); checkBlocked( grid ); } // end for System.out.print( cap ); System.out.print( blk ); } // end main() private static void checkBlocked( char[][] board ) { checkUpBlock( board ); checkLeftBlock( board ); checkRightBlock( board ); checkDownBlock( board ); } // end checkBlocked() private static void checkDownBlock( char[][] board ) { // need not check up because the marker is up of the target if( board[ row - 1 ][ col ] != '=' ) // if true, then must be 'x' or // 'o' { if( ( ( col - 1 < 1 ) || ( board[ row - 1 ][ col - 1 ] != '=' ) ) && ( ( row - 2 < 1 ) || ( board[ row - 2 ][ col ] != '=' ) ) && ( ( col + 1 > 8 ) || ( board[ row - 1 ][ col + 1 ] != '=' ) ) ) // end boolean expression { // body of if statement if( captured[ row - 1 ][ col ] != 'C' ) blk = blk + ( row - 1 ) + ", " + col + ", blocked\n"; } // end if } // if (board[row+1][col] != '=') } // end checkDownBlock( ) private static void checkRightBlock( char[][] board ) { // need not check left because the marker is left of the target // if true, then must be 'x' or 'o' if( board[ row ][ col + 1 ] != '=' ) { if( ( ( col + 2 > 8 ) || ( board[ row ][ col + 2 ] != '=' ) ) && ( ( row + 1 > 8 ) || ( board[ row + 1 ][ col + 1 ] != '=' ) ) && ( ( row - 1 < 1 ) || ( board[ row - 1 ][ col + 1 ] != '=' ) ) ) // end boolean expression { // body of if statement if( captured[ row ][ col + 1 ] != 'C' ) blk = blk + row + ", " + ( col + 1 ) + ", blocked\n"; } // end if ( body ... ) } // end if (board[row][col+1] != '=') } // end checkRightBlock( ) private static void checkLeftBlock( char[][] board ) { // need not check right because the marker is right of the target if( board[ row ][ col - 1 ] != '=' ) // if true, then must be 'x' or // 'o' { if( ( ( col - 2 < 1 ) || ( board[ row ][ col - 2 ] != '=' ) ) && ( ( row + 1 > 8 ) || ( board[ row + 1 ][ col - 1 ] != '=' ) ) && ( ( row - 1 < 1 ) || ( board[ row - 1 ][ col - 1 ] != '=' ) ) ) // end boolean expression { // body of if statement if( captured[ row ][ col - 1 ] != 'C' ) blk = blk + row + ", " + ( col - 1 ) + ", blocked\n"; } // end if } // end if (board[row][col-1] != '=') } // end checkLeftBlock( ) private static void checkUpBlock( char[][] board ) { // need not check down because the marker is down of the target if( board[ row + 1 ][ col ] != '=' ) // if true, then must be 'x' or // 'o' { if( ( ( col - 1 < 1 ) || ( board[ row + 1 ][ col - 1 ] != '=' ) ) && ( ( row + 2 > 8 ) || ( board[ row + 2 ][ col ] != '=' ) ) && ( ( col + 1 > 8 ) || ( board[ row + 1 ][ col + 1 ] != '=' ) ) ) // end boolean expression { // body of if statement if( captured[ row + 1 ][ col ] != 'C' ) blk = blk + ( row + 1 ) + ", " + col + ", blocked\n"; } // end if } // if (board[row+1][col] != '=') } // end checkUpBlock( ) private static void checkCaptured( char[][] board ) { checkUpCap( board ); checkLeftCap( board ); checkRightCap( board ); checkDownCap( board ); } // end checkCaptured( ) private static void checkUpCap( char[][] board ) { char friend = 'x', foe = 'o'; if( marker == 'o' ) { friend = 'o'; foe = 'x'; } int begin = row + 1, end = 0; for( int i = 7; i > row; i-- ) { if( board[ i + 1 ][ col ] == friend ) { end = i + 1; for( int j = i; j > row; j-- ) if( board[ j ][ col ] == foe ) begin = j; else { begin = 0; break; } } // end if } // end for boolean newTerm = true; String capUp = ""; // building output if( begin > 0 ) { for( int i = begin; i < end; i++ ) { if( newTerm == false ) capUp = capUp + " and "; newTerm = false; capUp = capUp + i + ", " + col; captured[ i ][ col ] = 'C'; } // end for if( capUp.length() > 0 ) cap = cap + capUp + ", captured\n"; } } // end checkUpCap( ) private static void checkDownCap( char[][] board ) { char friend = 'x', foe = 'o'; if( marker == 'o' ) { friend = 'o'; foe = 'x'; } int begin = 0; // checking left from first possible 'o' to just before NEW x. // don't re-enter for loop after begin>0 as stream is found. for( int i = 2; i < row && begin == 0; i++ ) { if( row - i > 0 && board[ row - i ][ col ] == friend ) // for( int j = 1; j < i; j++ ) if( board[ row - j ][ col ] == foe ) begin = row - j; else { begin = 0; break; } } // end checking down boolean newTerm = true; String capDown = ""; // building output if( begin > 0 ) for( int i = begin; i < row; i++ ) { if( newTerm == false ) capDown = capDown + " and "; newTerm = false; capDown = capDown + i + ", " + col; captured[ i ][ col ] = 'C'; } // end for if( capDown.length() > 0 ) cap = cap + capDown + ", captured\n"; } // end checkDownCap( ) private static void checkRightCap( char[][] board ) { char friend = 'x', foe = 'o'; if( marker == 'o' ) { friend = 'o'; foe = 'x'; } int begin = col + 1, end = 0; for( int i = 7; i > col; i-- ) { if( board[ row ][ i + 1 ] == friend ) { end = i + 1; for( int j = i; j > col; j-- ) if( board[ row ][ j ] == foe ) begin = j; else { begin = 0; break; } } // end if } // end checking right boolean newTerm = true; String capRight = ""; // building output if( begin > 0 ) for( int i = begin; i < end; i++ ) { if( newTerm == false ) capRight = capRight + " and "; newTerm = false; capRight = capRight + row + ", " + i; captured[ row ][ i ] = 'C'; } // end for if( capRight.length() > 0 ) cap = cap + capRight + ", captured\n"; } // end checkRightCap( ) private static void checkLeftCap( char[][] board ) { char friend = 'x', foe = 'o'; if( marker == 'o' ) { friend = 'o'; foe = 'x'; } int begin = 0; // checking left from first possible 'o' to just before NEW x. // don't re-enter for loop after begin>0 as stream is found. for( int i = 2; i < col && begin == 0; i++ ) { if( col - i > 0 && board[ row ][ col - i ] == friend ) // for( int j = 1; j < i; j++ ) if( board[ row ][ col - j ] == foe ) begin = col - j; else { begin = 0; break; } } // end checking left boolean newTerm = true; String capLeft = ""; // building output if( begin > 0 ) for( int i = begin; i < col; i++ ) { if( newTerm == false ) capLeft = capLeft + " and "; newTerm = false; capLeft = capLeft + row + ", " + i; captured[ row ][ i ] = 'C'; } // end for if( capLeft.length() > 0 ) cap = cap + capLeft + ", captured\n"; } // end checkLeftCap( ) private static void printGrid( char[][] board ) { // Visual feedback for analysis for( int i = 8; i > 0; i-- ) { System.out.print( i ); for( int j = 1; j <= 8; j++ ) System.out.print( " " + board[ i ][ j ] ); System.out.println(); } System.out.println( " 1 2 3 4 5 6 7 8\n" ); } // end printGrid() private static char[][] addMarker( char[][] board, int item ) throws IOException { // System.out.println("item = " + item ) ; row = coord[ item ][ 0 ]; col = coord[ item ][ 1 ]; board[ row ][ col ] = marker; return board; } private static int grabData() throws IOException { BufferedReader in = new BufferedReader( new FileReader( "Petteia.in" ) ); String line = in.readLine(); int numOfLocations = Integer.parseInt( line ); coord = new int[ numOfLocations ][ 2 ]; for( int i = 0; i < numOfLocations; i++ ) { line = in.readLine(); // Check StringTokenizer in API. Delimiter can be any string. StringTokenizer st = new StringTokenizer( line, ", " ); row = Integer.parseInt( st.nextToken() ); col = Integer.parseInt( st.nextToken() ); coord[ i ][ 0 ] = row; coord[ i ][ 1 ] = col; } // end for return numOfLocations; } // end grabData() private static char[][] initializeGrid() throws IOException { // Remember that last cell in array is length + 1 // Grid is 1..8, so array must be 0..9 to yield [1]..[8] // But extra row and col [10][10] to place '=' for analysis char board[][] = new char[ 10 ][ 10 ]; // initialize all squares with '=' for( int i = 0; i < 10; i++ ) for( int j = 0; j < 10; j++ ) board[ i ][ j ] = '='; return board; } // end initializeGrid() } // end class Petteia