import java.io.*; import java.util.*; import java.awt.geom.*; /** * Solution to Checkers * * @author vanb */ public class checkers_vanb { public Scanner sc; public PrintStream ps; /** * A Node will represent a square on the board * where a Black king can be. * * @author vanb */ public class Node { // Useful for searching public boolean visited = false; // These represent Jumps public List edges = new LinkedList(); // Useful fpor debugging public String label; /** * Create a Node * * @param label A debugging label for this node */ public Node( String label ) { this.label = label; } /** * Use DFS to count the number of nodes we can reach. * * @return The number of nodes reachable from here */ public int dfscount() { int count = 0; if( !visited ) { count = 1; visited = true; for( Edge edge : edges ) if( !edge.visited ) { count += edge.othernode( this ).dfscount(); } } return count; } /** * Use DFS to clear the "visited" flag */ public void dfsclear() { if( visited ) { visited = false; for( Edge edge : edges ) if( !edge.visited ) { edge.othernode( this ).dfsclear(); } } } /** * A Pretty String for debugging * * @return A pretty String for debugging */ public String toString() { return label; } /** * Add an Edge, making sure that it isn't a duplicate. * * @param e Edge to add */ public void addEdge( Edge e ) { boolean duplicate = false; for( Edge edge : edges ) { if( edge.fromnode==e.fromnode && edge.tonode==e.tonode) duplicate = true; if( edge.fromnode==e.tonode && edge.tonode==e.fromnode) duplicate = true; } if( !duplicate ) edges.add( e ); } } /** * This class represents an Edge in the graph, which is a Jump on the board. * * @author vanb */ public class Edge { // Have we used this node in Fleury's Algorithm? public boolean visited = false; // The nodes that this edge runs between public Node fromnode, tonode; /** * Create an Edge. * * @param fromnode One endpoint * @param tonode The other endpoint */ public Edge( Node fromnode, Node tonode ) { this.fromnode = fromnode; this.tonode = tonode; } /** * Get the node that is connected to the given node by this Edge. * * @param node An endpoint of the Edge * @return The other endpoint */ public Node othernode( Node node ) { return fromnode==node ? tonode : fromnode; } public String toString() { return fromnode + (visited?"X":"-") + tonode; } } /** * This class represents a Move in a Breadth-first Searc. * * @author vanb */ public class Move { public int i, j; public Node from; /** * Build a Move. * * @param i Row of the board we're moving to * @param j Column of the board we're moving to * @param from The Node we're coming from */ public Move( int i, int j, Node from ) { this.i = i; this.j = j; this.from = from; } /** * A pretty String for debugging. * * @return A pretty String for debugging */ public String toString() { return "[" + i + "," + j + "]"; } } /** This will represent the board as characters. */ char board[][]; /** This will represent the board as nodes in a graph. */ Node nodes[][]; /** * Get a character from the board, handling off-the-board indices. * * @param i Row * @param j Column * @return Character at board[][j], or '?' if (i,j) is off the board. */ public char getchar( int i, int j ) { char result = '?'; if( i>=0 && i=0 && jwithoutedge; } /** * Driver. * @throws Exception */ public void doit() throws Exception { sc = new Scanner( System.in ); ps = System.out; int n = sc.nextInt(); board = new char[n][]; nodes = new Node[n][n]; for( int i=0; i q = new LinkedList(); // Test every Black King for( int i=0; i