裸爆搜。但是要注意搜索方法..
可参考http://blog.csdn.net/lyy289065406/article/details/6642595
#include<stdio.h> #include<string.h> #include<algorithm> #include<set> using namespace std; int a[10][10]; char c[10][10]; int tt; bool flag; void flip(int x, int y) { a[x][y] = 1 - a[x][y]; a[x+1][y] = 1 - a[x+1][y]; a[x-1][y] = 1 - a[x-1][y]; a[x][y-1] = 1 - a[x][y-1]; a[x][y+1] = 1 - a[x][y+1]; } int OK() { int x = 0; for( int i = 1; i <= 4; i ++ ) for( int j = 1; j <= 4; j ++ ) x += a[i][j]; if( x == 0 || x == 16 ) return 1; else return 0; } void dfs(int x, int y, int t) { if( t == tt ) { flag = OK(); return; } if( flag || x == 5 ) return; flip(x, y); if( y < 4 ) dfs(x, y+1, t+1); else dfs(x+1, 1, t+1); flip(x, y); if( y < 4 ) dfs(x, y+1, t); else dfs(x+1, 1, t); return; } int main() { while(~scanf("%s", c[1]+1)) { for( int i = 2; i <= 4; i ++ ) { scanf("%s", c[i] + 1); } for( int i = 1; i <= 4; i ++ ) { for( int j = 1; j <= 4; j ++ ) a[i][j] = (c[i][j] == 'w' ? 0: 1); } flag = 0; for( tt = 0; tt <= 16; tt ++ ) { dfs(1, 1, 0); if( flag ) break; } if( flag ) printf("%d\n", tt); else printf("Impossible\n"); } return 0; } /* bwwb bbwb bwwb bwww */