bwwbbbwbbwwbbwwwSample Output4解题报告
不要想太复杂就好,要明确如果有答案,那么答案小于等于8#include<stdio.h>#include<string.h>bool map[6][6];int ox[]={0,0,0,1,-1};int oy[]={0,1,-1,0,0};int best;bool check(){ //end check for(int j=1;j<=4;j++) for(int k=1;k<=4;k++) if(map[1][1]!=map[j][k]) return false; return true;}void op(int X,int Y){ for(int i=0;i<5;i++){ int x=X+ox[i]; int y=Y+oy[i]; map[x][y]=!map[x][y]; }}void dfs(int t,int cnt){ if(check()){ if(cnt<best) best=cnt; return ; } if(cnt>best||t>16) return ; int X=t%4+1; int Y=t/4+1; //剪枝 加上该条件 78ms立马变0ms if(Y>1&&X>1&&map[X-1][Y-1]!=map[1][1]) return ; dfs(t+1,cnt); op(X,Y); dfs(t+1,cnt+1); op(X,Y);}int main(){ char str[5]; for(int i=1;i<=4;i++){ scanf("%s",str); for(int j=1;j<=4;j++) map[i][j]=str[j-1]=='b'; } best=9; dfs(0,0); if(best<9) printf("%d/n",best); else puts("Impossible"); return 0;}
新闻热点
疑难解答