#include<string>#include<iostream>#include<utility>#include<vector>#include<queue>#include<ctype.h>usingnamespacestd;/** DEBUG ONLY: If compiled with -DDEBUG, each dataset will be printed back out* to stderr with all bricks on the shortest path marked with lowercase letters.*//* Maximum width and height allowed by the problem statement */#defineROWS 20#defineCOLS 20/* A convenient way to represent a single coordinate */typedefpair<int, int> point;/* Number of cells adjacent to any other given cell */#defineDIRS 4/* Movement cost used as starting point for shortest path algorithm */#defineMAXCOST(std::numeric_limits<int>::max())/* List of all possible directions that one can move from one cell to another */point dir[] = {point( 0, -1 ),point( 0, +1 ),point( -1, 0 ),point( +1, 0 ), };/* Data structure representing a single unit in the wall */typedefstructcell_s { char letter;/* Letter assigned to this unit as read in from the input *//* These fields are used by Dijkstra's algorithm in shortest_path() */point prev;/* DEBUG ONLY: Coordinate of previous cell on shortest path */int cost;/* Tentative shortest path cost to this cell */} cell_t;/* Array representing the entire wall */cell_t wall[ROWS][COLS];/* Wall height and width for current data set */int rows, cols;/** Comparison function object required for priority_queue<point> in* shortest_path. Since each point in the queue refers to a specific cell_t in* the grid, this function object compares the costs associated with the two* cells. A greater than (>) comparison produces a priority queue with the* smallest cost node on top.*/classcost_compare {public:inlinebooloperator()(pointconst&a, pointconst&b)const{ int cost1 = wall[a.first][a.second].cost; int cost2 = wall[b.first][b.second].cost;returncost1 > cost2; } };#ifdefDEBUG/** DEBUG ONLY: This function implements a simple recursive flood fill algorithm* that starts at unit [row][col] in the wall and changes wall[i][j].letter to* lowercase for every (ith, jth) adjacent wall unit that is part of the same* brick (i.e. based on the letter "match"). Used for debug outout to show which* bricks have to be removed on the shortest path.*/voidflood_fill(int row, int col, char match) {/* Stop recursing if coordinate (row, col) is outside of the wall */if(row < 0 || col < 0 || row >= rows || col >= cols) {return; } char &letter = wall[row][col].letter;/* Stop if this is not the unit we're looking for */if(letter != match) {return; }/* Stop if this wall unit has already been converted to lowercase */if(islower(letter)) {return; }/* Convert this wall unit's letter to lowercase */letter =tolower(letter);/* Recursively flood fill all neighbors of this unit */for(int i = 0; i < DIRS; i++) {flood_fill(row + dir[i].first, col + dir[i].second, match); } }/** DEBUG ONLY: Print out the overall shortest path in the wall by converting* all bricks along that path to lowercase letters. This function makes use of* flood_fill() to mark every brick along the shortest path starting from* the brick at column "endcol" in the bottom most row.*/voidprint_path(int endcol) {/* Starting location for shortest path in the bottom most row */pointloc(rows - 1, endcol);/* Follow the shortest path in reverse, marking every brick along the way */while(loc !=point(-1, -1)) { int row = loc.first; int col = loc.second;flood_fill(row, col, wall[row][col].letter); loc = wall[row][col].prev; }/* Print out brick letter grid after marking the shortest path on it */for(int row = 0; row < rows; row++) {for(int col = 0; col < cols; col++) { cerr << wall[row][col].letter; } cerr << endl; } }#endif/** Run Dijkstra's algorithm starting with the cell at column "start" in the* top row, and return the shortest path found to any cell in the bottom row.* DEBUG ONLY: If the "print" flag is specified, the shortest path is printed* out to stderr.*/intshortest_path(int start, bool print) {/* Priority queue for picking the next least cost wall unit */priority_queue<point, vector<point>, cost_compare> queue;/* Initialize data grid */for(int row = 0; row < rows; row++) {for(int col = 0; col < cols; col++) { wall[row][col].prev =point(-1, -1); wall[row][col].cost = MAXCOST; } }/* Setup the starting cell as required by Dijkstra's algorithm */wall[0][start].cost = 1; queue.push(point(0, start) );/* Keep running Dijkstra until all nodes are visited */while(!queue.empty()) {/* Remove the closest cell from the priority queue */int row = queue.top().first; int col = queue.top().second; queue.pop();/* Check all adjacent cells to this one */for(int i = 0; i < DIRS; i++) { int cost;/* The coordinate of the adjacent cell */int newrow = row + dir[i].first; int newcol = col + dir[i].second;/* Skip this coordinate point if it's outside the wall */if(newrow < 0 || newcol < 0 || newrow >= rows || newcol >= cols) {continue; }/* Edge cost is 0 to same brick and 1 to different brick */cost = wall[row][col].letter == wall[newrow][newcol].letter ? 0 : 1;/* Check if real cost is smaller than tentative cost */if(wall[row][col].cost + cost < wall[newrow][newcol].cost) {/* Adjust tentative cost and enqueue adjacent cell */wall[newrow][newcol].cost = wall[row][col].cost + cost; wall[newrow][newcol].prev =point(row, col); queue.push(point(newrow, newcol) ); } } } int mincost = MAXCOST; int endcol = 0;/* Return the shortest path found to any bottom row from "start" column */for(int col = 0; col < cols; col++) { int cost = wall[rows - 1][col].cost;if(cost < mincost) { mincost = cost; endcol = col; } }#ifdefDEBUG/* DEBUG ONLY: Print out the overall shortest path */if(print) {print_path(endcol); }#endifreturnmincost; }/** Compute and return the minimum number of bricks that have to be removed to* create a gap in the wall. The entire wall can be treated as a graph where* each wall unit (or cell) is a node in the graph and there exists an edge* from every cell to each of the 4 adjacent cells. If that edge leads to a* cell with the same letter (and therefore part of the same brick), then the* cost of that edge is 0; if the edge leads to a different brick the edge* cost is 1. Computing all pairs shortest paths and then finding the minimum* length path between any cell in the top row and any cell in the bottom row,* will give the minimum number of bricks to remove.** In this solution Dijkstra's algorithm is run once for each of the cells in* the top most row to obtain the same result.** Potential Optimization: An extra dummy row can be added either on the top* or the bottom of the wall. If this row is treated as a single brick that* is distinct from all other bricks, then just one pass of Dijkstra's would be* enough.*/intanalyze(void) { int mincost = MAXCOST; int startcol = 0;/* Find shortest path from each top row cell to any bottom row cell */for(int col = 0; col < cols; col++) { int cost =shortest_path(col,false);if(cost < mincost) { mincost = cost; startcol = col; } }#ifdefDEBUG/* DEBUG ONLY: Recompute and print out the overall shortest path */shortest_path(startcol,true);#endifreturnmincost; }/* Main body of program */voidprocess(void) { int data_num, data_idx;/* Read how many data sets to process */cin >> data_num;/* Process each data set separately */for(data_idx = 0; data_idx < data_num; data_idx++) { int row, col;/* Read in the height and width of this wall */cin >> rows >> cols;/* SANITY CHECK: Make sure the wall size is within limits */if(rows <= 0 || cols <= 0 || rows > ROWS || cols > COLS) { cerr << "Bad wall size: " << rows << " " << cols << endl;throw; }/* Read in the brick wall representation into array */for(row = 0; row < rows; row++) {for(col = 0; col < cols; col++) { char c; cin >> c; wall[row][col].letter = c;/* SANITY CHECK: Make sure wall units are valid letters */if(!isupper(c)) { cerr << "Bad wall unit character: " << c << endl;throw; } } }/* Compute and printout the smallest number of bricks to remove */int mincost =analyze(); cout << mincost << endl;#ifdefDEBUG cerr << mincost << endl;#endif} }/* Run program and print out any exceptions that occur */intmain(void) {/* Throw exceptions on failed data extraction in >> operator */cin.exceptions(ios::failbit);/* Run main body of code */try{process(); }/* Catch unexpected EOF or bad input data */catch(ios::failureconst&e) { cerr << "Unexpected EOF or data type mismatch on input" << endl; }return0; }