/********************************************************************* Problem: Petteia Competition: American Computer Science League #3 Section: Intermediate 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 BufferedReader in; static private String output = ""; static public void main( String[] args ) throws IOException { in = new BufferedReader( new FileReader( "Petteia.in" ) ); char[][] grid = initializeGrid(); // printGrid( grid ) ; for( int i = 0; i < 5 ; i++ ) { capturedOhs( grid ); if( output.equals( "" ) ) System.out.println( "NONE" ); else System.out.println( output ); output = ""; } } // end main() private static void capturedOhs( char[][] board ) throws IOException { StringTokenizer st = new StringTokenizer( in.readLine(), ", " ); int row = Integer.parseInt( st.nextToken() ); int col = Integer.parseInt( st.nextToken() ); char oldSquare = board[ row ][ col ]; board[ row ][ col ] = 'N'; // N == the new x // System.out.println("\n\n") ; printGrid( board ) ; checkLeft( board, row, col ); checkRight( board, row, col); checkDown( board, row, col); checkUp( board, row, col ); board[ row ][ col ] = oldSquare; // reinstate square as before. } // end capturedOhs( ) private static void checkUp( char[][] board, int row, int col ) { int begin = row + 1, end = 0; for( int i = 7; i > row; i-- ) { if( board[ i + 1 ][ col ] == 'x' ) { end = i + 1; for( int j = i; j > row; j-- ) if( board[ j ][ col ] == 'o' ) begin = j; else { begin = 0; break; } } // end if } // end for // building output if( begin > 0 ) for( int i = begin; i < end; i++ ) { // if output.length() > a single coordinate set // then place " and " before further coordinates if( output.length() > 3 ) output = output + " and "; output = output + i + ", " + col; } // end for } // end checkUp( ) private static void checkDown( char[][] board, int row, int col ) { 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 ] == 'x' ) // for( int j = 1; j < i; j++ ) if( board[ row - j ][ col ] == 'o' ) begin = row - j; else { begin = 0; break; } } // end checking left // System.out.println("\n\nrow = " + row + "\tcol = " + col + "\tbegin = " + begin) ; // printGrid( board ) ; // building output if( begin > 0 ) for( int i = begin; i < row; i++ ) { // if output.length() > a single coordinate set // then place " and " before further coordinates if( output.length() > 3 ) output = output + " and "; output = output + i + ", " + col; } // end for } // end checkDown( ) private static void checkRight( char[][] board, int row, int col ) { int begin = col + 1, end = 0; for( int i = 7; i > col; i-- ) { if( board[ row ][ i + 1 ] == 'x' ) { end = i + 1; for( int j = i; j > col; j-- ) if( board[ row ][ j ] == 'o' ) begin = j; else { begin = 0; break; } } // end if } // end checking right // building output if( begin > 0 ) for( int i = begin; i < end; i++ ) { // if output.length() > a single coordinate set // then place " and " before further coordinates if( output.length() > 3 ) output = output + " and "; output = output + row + ", " + i; } // end for } // end checkRight( ) private static void checkLeft( char[][] board, int row, int col ) { 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 ] == 'x' ) // for( int j = 1; j < i; j++ ) if( board[ row ][ col - j ] == 'o' ) begin = col - j; else { begin = 0; break; } } // end checking left // building output if( begin > 0 ) for( int i = begin; i < col; i++ ) { // if output.length() > a single coordinate set // then place " and " before further coordinates if( output.length() > 3 ) output = output + " and "; output = output + row + ", " + i; } // end for } // end checkLeft( ) 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[][] 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 = 1; j < 10; j++ ) board[ i ][ j ] = '='; String line = in.readLine(); // Check StringTokenizer in API. Delimiter can be any string. StringTokenizer st = new StringTokenizer( line, ", " ); int numOfOs, numOfXs, row, col; numOfOs = Integer.parseInt( st.nextToken() ); for( int i = 0; i < numOfOs; i++ ) { row = Integer.parseInt( st.nextToken() ); col = Integer.parseInt( st.nextToken() ); board[ row ][ col ] = 'o'; } st = new StringTokenizer( in.readLine(), ", " ); numOfXs = Integer.parseInt( st.nextToken() ); for( int i = 0; i < numOfXs; i++ ) { row = Integer.parseInt( st.nextToken() ); col = Integer.parseInt( st.nextToken() ); board[ row ][ col ] = 'x'; } return board; } // end initializeGrid() } // end class Petteia /* Screen Dump From Competitor's Input 6, 3 5, 4 and 5, 5 5, 4 and 5, 5 and 6, 3 NONE NONE */ /* Screen Dump From Testing Input 2, 2 3, 6 and 3, 7 2, 2 2, 2 and 2, 4 3, 6 and 3, 7 */