贴上自己巨丑的暴搜代码:
#include <stdio.h> bool s[20][20]; int best; int check() { int i, j, tot = 0; for(i=0;i<4;i++) for(j=0;j<4;j++) tot +=s[i][j]; if(tot == 0 || tot == 16) return 1; return 0; } void Echange(int x, int y) { s[x][y] = !s[x][y]; s[x+1][y] = !s[x+1][y]; s[x][y+1] = !s[x][y+1]; if(x>0) s[x-1][y] = !s[x-1][y]; if(y>0) s[x][y-1] = !s[x][y-1]; } void Search(int k, int ans) { int x, y; if(16 == k) { if( check()&& ans <best) best = ans; }else { x = k /4; y = k %4; Search(k+1,ans); Echange(x, y); Search(k+1,ans+1); Echange(x, y); } } void work() { int i, j; char c; for(i = 0; i<4; i++) { for(j = 0; j<4; j++){ scanf("%c", &c); if(c=='w') s[i][j] = 0; else s[i][j] = 1; } getchar(); } //for(i=0;i<4;i++){for(j=0;j<4;j++) printf("%d",s[i][j]);printf("\n");} best = 1000; Search(0, 0); for(i=0;i<4;i++) for(j=0;j<4;j++) s[i][j] =!s[i][j]; Search(0, 0); if(best != 1000) printf("%d\n",best); else printf("Impossible\n"); } int main() { work(); return 0; }
时间复杂度 2^16.稳过。。。
过不我还想的了这题跟开关问题很像,应该可以优化。
呵呵,留着下次再写。