这道题目的难点是理解最多有2^16次方种可能,需要理解每个棋子只能翻一次或者不翻。这么这道题目就可以用DFS暴力解决!
#include<stdio.h> char a[4][4]; int map[4][4]; int min=99999; int t; void dfs(int step); void flip(int x,int y){ map[x][y]=!map[x][y]; if(x>=1) map[x-1][y]=!map[x-1][y]; if(x<=2) map[x+1][y]=!map[x+1][y]; if(y>=1) map[x][y-1]=!map[x][y-1]; if(y<=2) map[x][y+1]=!map[x][y+1]; } bool judge(){ for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(map[i][j]!=map[0][0]) return 0; return 1; } int main(){ for(int i=0;i<4;i++) scanf("%s",&a[i]); for(int i=0;i<4;i++) for(int j=0;j<4;j++) if(a[i][j]=='b') map[i][j]=0; else map[i][j]=1; t=0; dfs(0); if(min==99999) printf("Impossible"); else printf("%d",min); return 0; } void dfs(int step){ if(step==16) { if(judge()) if(min>=t) min=t; return; } for(int i=0;i<2;i++){ if(i==0) dfs(step+1); else{ flip(step/4,step%4); t++; dfs(step+1); flip(step/4,step%4); t--; } } }