POJ – 1753 – FLIP GAME = Enumeration

By Game

http://poj.org/problem?id=1753

Question meaning: 4*4 square matrix, every time you flip the surrounding chess pieces, ask the minimum number of moves for all the same color.

It seems that cf has a question like this, usually the first line is enumerated, and then the first line can only be affected from the second line if it is not turned, so that the first three lines can be single Click to adjust, if the last line is not all the same color, just false. 

#include#include#include#include#include#include#include#include< stack>#include#include#includeusing namespace std;typedef long long ll;char cg[6][6];char g[6][6];inline void copyg() { memcpy(g, cg, sizeof(cg));}inline void flip(int i, int j) {g[i][j] = !g[i][j]; g[i-1][j] = !g[i-1][j]; g[i + 1][j] = !g[i + 1][j]; g[i][j-1] = !g[i][j -1]; g[i][j + 1] = !g[i][j + 1]; /*for(int i = 1; i <= 4; ++i) {for(int j = 1 ; j <= 4; ++j) {printf("%d", (int)g[i][j]);} printf("
");} printf("
");*/ }int main() {#ifdef Yinku freopen("Yinku.in", "r", stdin);#endif // Yinku for(int i = 1; i <= 4; ++i) {scanf("% s", cg[i] + 1); for(int j = 1; j <= 4; ++j) {cg[i][j] = (cg[i][j] =='b') ? 0: 1;}} int minans = 1e9; for(int k = 0; k <(1 << 4); ++k) {copyg(); int cnt = 0; for(int j = 0; j <4; ++j) {if((k >> j) & 1) {flip(1, j + 1); ++cnt;}} for(int i = 1; i <= 3; ++i) {for(int j = 1; j <= 4; ++j) {if(g[i][j] == 1) {flip(i + 1, j); ++cnt;}}} int suc = 1; for(int j = 1; j <= 4; ++j) {if(g[4][j] == 1) {suc = 0; break;} } if(suc) {minans = min(minans, cnt);} copyg(); cnt = 0; for(int j = 0; j <4; ++j) {if((k >> j) & 1 ) {flip(1, j + 1); ++cnt;}} for(int i = 1; i <= 3; ++i) {for(int j = 1; j <= 4; ++j) {if(g[i][j] == 0) {flip(i + 1, j); ++cnt;}}} suc = 1; for(int j = 1; j <= 4; + +j) {if(g[4][j] == 0) {suc = 0; break;}} if(suc) {minans = min(minans, cnt);}} if(minans >= 10000) puts ("Impossible"); else printf("%d
", minans);}

, , ,

Leave a Comment

Your email address will not be published.