## SRM 663 D2 250-Pointer (ChessFloor)

### James S. Plank

Sat Nov 12 01:08:15 EST 2016
The key to this problem, in my opinion, is to not try to be too smart about it. Treat it as an enumeration problem -- enumerate all combinations of square colors, and for each combination, calculate how many changes it takes to make the checkerboard with that combination. There are 26*25 = 650 combinations of lower case letters that don't equal each other. For each of these, calculate the number of changes, and keep track of the minimum.
Solution.cpp

 ```#include #include #include #include #include using namespace std; class ChessFloor { public: int minimumChanges(vector floor); }; int ChessFloor::minimumChanges(vector floor) { int i, j, b, w; int best, nc; /* Sentinelize best so that it is bigger than any legal answer. */ best = floor.size() * floor.size() + 1; /* Enumerate all combinations of "black" and "white" */ for (b = 'a'; b <= 'z'; b++) { for (w = 'a'; w <= 'z'; w++) { if (b != w) { /* For each of these, calculate the number of squares that you have to change to make it work. */ nc = 0; for (i = 0; i < floor.size(); i++) { for (j = 0; j < floor.size(); j++) { if ((i+j)%2 == 0 && floor[i][j] != b) nc++; if ((i+j)%2 == 1 && floor[i][j] != w) nc++; } } /* Keep track of the minimum */ if (nc < best) best = nc; } } } /* Return the minimum */ return best; } ```