题目链接
题目大意：一个4*4的方格，上面黑白棋都有，可以任意翻转其中的一个旗子，但是这个旗子的上下左右都要跟着反转（白变黑，黑变白）
求最少次数使得棋谱全黑或全白
一个位置无非就是翻或者不翻，翻得话连动身边的一起翻，复杂度就是2^16*4，不大
果断深搜，要注意回溯，一个点翻转之后，要再次翻回来，避免一个状态的改变
#include<iostream> #include<algorithm> #include<map> #include<string> using namespace std; const int INF=1<<29; int maxn=INF; int ma[10][10]={0}; int pd(){ int sum=0; for(int i=0;i<4;i++){ for(int j=0;j<4;j++) sum+=ma[i][j]; } return sum==0; } void change(int i,int j){ ma[i][j]=!ma[i][j]; if(i+1<=3) ma[i+1][j]=!ma[i+1][j]; if(i-1>=0) ma[i-1][j]=!ma[i-1][j]; if(j+1<=3) ma[i][j+1]=!ma[i][j+1]; if(j-1>=0) ma[i][j-1]=!ma[i][j-1]; } void dfs(int i,int j,int sum){ if(pd()){ if(sum<maxn) maxn=sum; return; } if(i>3) return; if(j+1<=3){ dfs(i,j+1,sum); change(i,j+1); dfs(i,j+1,sum+1); change(i,j+1); } else{ dfs(i+1,0,sum); change(i+1,0); dfs(i+1,0,sum+1); change(i+1,0); } } int main(){ for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ char c; cin>>c; if(c=='b') ma[i][j]=1; } } dfs(0,0,0); change(0,0); dfs(0,1,1); if(maxn==INF) cout<<"Impossible"<<endl; else cout<<maxn<<endl; return 0; }
