#include<iostream>#include<limits>#include<ext/hash_map>usingnamespacestd;/** NOTE: hash_map is not in the C++ standard so it's anybody's guess which* include file and namespace it might be located in at the moment.*/usingnamespace__gnu_cxx;/* Total number of columns in board (including blank spaces) */#defineCOLS 5/* Total number of rows in board (actually rows of pegs) */#defineROWS 5/** Since solving this problem may require moderately deep recusrion, using a* bit vector to represent the board helps conserve stack space to avoid any* overflows. Each space on the board is represented with a single bit, where* a one bit indicates a peg is in place. The board is layed out in the vector* in row major order, with location [0][0] being the LSb in the vector. A bit* vector also makes a convenient hashing key since the value of the bit vector* as an integer can be used as the hash for caching.*/int global_board;/** Since the board is cross shaped, this vector defines those areas on the* board that a peg can or cannot move to (i.e. those represented by a '#' in* the input). A 1 bit indicates a valid square that pegs can move to.*/int valid;/** Since many different search paths can lead to the same board configuration* the search can be optimized by caching already explored boards and not* having to search them again. The hash table is indexed by the board* configuraton itself which can be conviniently represented as a single* integer.*/hash_map<int, bool> cache;/** This object is thrown as an exception in the main algorithm code if the* most possible optimal solution of only 1 peg ramaining is found. This* avoids wasting time searching for a more optimal solution if the most* optimally possible one was already found.*/classtraverse_exit { };/* Helper macro for computing bit position in the bit vector */#defineMASK(row, col) (1 << (((row) * COLS) + (col)))/* Helper macro for testing/setting/clearing bit vector values */#defineTST(vector, row, col) ((vector) &MASK((row), (col)))#defineSET(vector, row, col) ((vector) |=MASK((row), (col)))#defineCLR(vector, row, col) ((vector) &= ~MASK((row), (col)))/* The total number of pegs remaining for the best case computed so far */int global_total;/* Copy of board layout for an optimal solution (for debug only) */int optimal_board;/* Initialize board layout from the input */voidparse_board(void) { int row, col;/* Iterate over all rows and columns */for(row = 0; row < ROWS; row++) {for(col = 0; col < COLS; col++) { char c;/* Parse the next input character */cin >> c;switch(c) {/* A hash denotes invalid spaces where no peg can go */case'#':CLR(valid, row, col);CLR(global_board, row, col);break;/* A period indicates a valid space but with no peg on it */case'.':SET(valid, row, col);CLR(global_board, row, col);break;/* A lowercase o indicates a valid space with a peg on it */case'o':SET(valid, row, col);SET(global_board, row, col);break;/* Any other character is invalid */default:throw"Invalid input character"; } } } }#ifdefDEBUG/* Print out a given board solution (for debugging purposes only) */voidprint_board(int board) { int row, col;/* Iterate over all rows and columns */for(row = 0; row < ROWS; row++) {for(col = 0; col < COLS; col++) {/* Print out a '#' for invalid spaces */if(!TST(valid, row, col)) cout << '#';/* Print out a 'o' for spaces with a peg in them */elseif(TST(board, row, col)) cout << 'o';/* Print out a '.' for empty spaces */elsecout << '.'; } cout << endl; } }#endifvoidtraverse(int board, int total);/** Given a peg location on the board and a direction to move it in, attempt* the move, calling traverse() with a new copy of the board if the move* is possible.** A peg can be moved under these circuimstances:** 1. Not too close to the edge (already checked for in traverse())* 2. Not trying to move into an invalid square* 3. The next space over has a peg in it which this peg will jump* 4. The 2nd space over is empty for the current peg to jump into** board - current instance of the board being considered* total - number of pegs in "board" (optimization to keep from recounting)* row - row number of peg to be moved* col - column number of peg to be moved* drow - +1/-1/0 if the peg is to move down/up/remain in same row* dcol - +1/-1/0 if the peg is to move right/left/remain in the same column*/voidmove(int board, int total, int row, int col, int drow, int dcol) { int drow2 = drow * 2; int dcol2 = dcol * 2;/* Cannot move if the next space over has no peg to jump */if(!TST(board, row + drow, col + dcol))return;/* Cannot move into an invalid square */if(!TST(valid, row + drow2, col + dcol2))return;/* Cannot move into an already occupied square */if(TST(board, row + drow2, col + dcol2))return;/* Update peg positions on the new board */CLR(board, row, col);CLR(board, row + drow, col + dcol);SET(board, row + drow2, col + dcol2);/* Call traverse() recursively with the new board */traverse(board, total - 1); }/** Given some board layout, try moving every peg on the board in all four* cardinal directions. If a move is successful, traverse() is called* recursively with a new copy of the board to compute possible moves from* that new layout, and so on. Recursion stops once no more pegs on the* board can be moved.** board - current instance of the board being considered* total - number of pegs in "board" (optimization to keep from recounting)*/voidtraverse(int board, int total) { int row, col;/* Record the current total if it is smaller than the best found so far */if(total < global_total) { global_total = total; optimal_board = board; }/** 1 or 0 (if the board had no pegs to begin with) pegs remaining is* the most possible optimal solution, therefore the search is aborted* to not waste any more time.*/if(global_total <= 1)throwtraverse_exit();/** If this board configuration has already been fully searched, do* not search it again.*/if(cache.find(board) != cache.end())return;/* Iterate over all rows and columns */for(row = 0; row < ROWS; row++) {for(col = 0; col < COLS; col++) {/** Look for any position with a peg in it, and then try moving the* peg in the four cardinal directions if it is not too close to* the edge of the board. The peg must be at least 2 spaces away* from the edge toward which it is moving.*/if(TST(board, row, col)) {/* Move left */if(col >= 2)move(board, total, row, col, 0, -1);/* Move right */if(col <= (COLS - 3))move(board, total, row, col, 0, +1);/* Move up */if(row >= 2)move(board, total, row, col, -1, 0);/* Move down */if(row <= (ROWS - 3))move(board, total, row, col, +1, 0); } } }/* Mark this board configuration as having been fully explored */cache[board] =true; }/* Count how many pegs are present on the board */intcount_pegs(int board) { int row, col, total = 0;/* Iterate over all rows and columns */for(row = 0; row < ROWS; row++) {for(col = 0; col < COLS; col++) {/* Invalid spaces are always initialized to have no pegs */if(TST(board, row, col)) total++; } }returntotal; }/* Main body of program */voidprocess(void) { int board_num, board_idx;/* Throw exceptions on unexpected EOF */cin.exceptions(ios::eofbit);/* Read how many boards are to be analyzed */cin >> board_num;/* Process each board separately */for(board_idx = 0; board_idx < board_num; board_idx++) { int i;/* Initialize bit vectors from input */parse_board();/* Initialize global total to least optimal value (i.e. INTMAX) */global_total = std::numeric_limits<int>::max();/* Clear out all previously cached results */cache.clear();/* Recursively explore all possible moves */try{traverse(global_board,count_pegs(global_board)); }catch(traverse_exit &e) {}/* Prinout out the results */#ifdefDEBUGprint_board(optimal_board);#endifcout << "The best case ends with " << global_total << " pegs." << endl; } }/* Run program and print out any exceptions that occur */intmain(void) {/* Run main body of code */try{process(); }/* Catch any internally generated exceptions */catch(charconst*e) { cerr << "Exception: " << e << endl; }/* Catch unexpected EOF on input */catch(ios::failureconst&ee) { cerr << "Exception: Unexpected EOF on input" << endl; }return0; }