题解：P1753 矩阵链排序问题

这道题是非常典型的翻牌问题了，网上看的好多是用了dfs，但我不是这么做的。。（这是很久之前看到的一个视频的做法。。）利用二进制思想，只枚举第一行的情况（2^n种），为了到达目的（所有的棋子和第一个棋子状态一样），以行为基准，从第二行开始，第i行中，如果第j列上边的那枚棋子(i-1,j)不符合情况，翻转自身(i,j)。这样前n-1行一定是符合标准的，最后判断第n行，从而判断这种方法对不对。AC代码如下：

#include #include #include #include using namespace std; const int INF=0x3f3f3f3f;

char a[7][7],s[7][7]; int n,ans; void change(int x,int y) { if(s[x][y]=='b') s[x][y]='w'; else s[x][y]='b'; } void flip(int x,int y) { change(x,y); if(x>1) change(x-1,y); if(y>1) change(x,y-1); if(x<n) change(x+1,y); if(y<n) change(x,y+1); }

void solve(char c,int tmp) //前n-1行全部翻成c并判断第n行 { for(int i=2;i<=n;i++) //注意这里要算n！ for(int j=1;j<=n;j++) if(s[i-1][j]!=c) //上一行不满足 { flip(i,j); //翻转自身 tmp++; } bool sign=true; for(int j=1;j<=n;j++) //判断最后一行是否符合要求 if(s[n][j]!=c) { sign=false; break; } if(sign) ans=min(ans,tmp); } int main() { memset(a,'\0',sizeof(a)); n=4; for(int i=1;i<=n;i++) scanf("%s",a[i]+1);//记录原始情况 ans=INF; for(int k=0;k<(1<<n);k++) //枚举第一行的情况 { memset(s,'\0',sizeof(s)); for(int i=1;i<=n;i++) //恢复原始情况 for(int j=1;j<=n;j++) s[i][j]=a[i][j]; int tmp=0; int kk=k; for(int i=0;i<n;i++) //一共n位 { int kk=(k>>i)&1; //第i位 if(kk==1) { tmp++; flip(1,n-i); //例如0101翻转第2和4个棋子 } } solve(s[1][1],tmp); //处理前n-1行情况与第一枚棋子相同（优化！） } if(ans==INF) printf("Impossible\n"); else printf("%d\n",ans); return 0; }