有m*n(m <=100,n <=100)个金币在桌面上排成一个m行n 列的金币阵列。每一枚金币或正面朝上或背面朝上。用数字表示金币状态，0表示金币正面朝上，1 表示背面朝上。
金币阵列游戏的规则是： （1）每次可将任一行金币翻过来放在原来的位置上；
（2）每次可任选2 列，交换这2 列金币的位置。
编程任务：给定金币阵列的初始状态和目标状态，编程计算按金币游戏规则，将金币阵列从初始状态变换到目标状态所需的最少变换次数。
Input
输入数据有多组数据。第1行有1 个正整数k，表示有k 组数据。每组数据的第1 行有2 个正整数m 和n。以下的m行是金币阵列的初始状态，每行有n 个数字表示该行金币的状态，0 表示金币正面朝上，1 表示背面朝上。接着的m行是金币阵列的目标状态。
Output
将计算出的最少变换次数按照输入数据的次序输出。相应数据无解时输出-1。
代码是别人的，感觉写的很好。写这个博客，主要是想要重温一下思路。
枚举1~m中，每一列为第一列的情况，
//从1~n行，找出不满足的行，进行一次行变换
//若是所枚举的这一列可以成功根据规则转换成目标矩阵，则，此时的矩阵与原矩阵的差别只会在列序上
此时，从i=2 列（第二列）开始与目标矩阵的第i列进行比较，
若不同，寻找本矩阵中第j列（就= i+1~m）是否有与目标矩阵的第i列相同的，若有，且 本矩阵第j列！= 目标矩阵第j列，则，进行一次列变换
//若是找不到符合条件的列，则所枚举的这一列为第一列是不可能按所给规则变换到目标矩阵的
1 #include<stdio.h> 2 3 const int inf = 99999; 4 const int N = 101; 5 6 int a[N][N],b[N][N],temp[N][N]; //a存储初始矩阵，b为目标状态矩阵 7 int n,m; 8 int need;//需要变换次数 9 10 void ChangeL(int x,int y)//变换列 11 { 12 if(x==y)return; 13 int i; 14 for(i=1;i<=n;i++) 15 { 16 int tt=temp[i][y]; 17 temp[i][y]=temp[i][x]; 18 temp[i][x]=tt; 19 } 20 need++; 21 } 22 23 void ChangeH(int x)//变换行 24 { 25 int i; 26 for(i=1;i<=m;i++) 27 { 28 temp[x][i]^=1; 29 } 30 } 31 32 33 bool Same(int x,int y) //判断列是否满足条件 34 { 35 int i; 36 for(i=1;i<=n;i++) 37 if(b[i][x]!=temp[i][y])return false; 38 return true; 39 } 40 41 42 int main() 43 { 44 int tests; 45 scanf("%d",&tests); //数据组数 46 47 while(tests--) 48 { 49 scanf("%d%d",&n,&m); //n行，m列 50 int i,j; 51 for(i=1;i<=n;i++) 52 for(j=1;j<=m;j++) 53 { 54 scanf("%d",&a[i][j]); 55 } 56 57 for(i=1;i<=n;i++) 58 for(j=1;j<=m;j++) 59 scanf("%d",&b[i][j]); 60 61 int k; 62 int ans=inf; //ans存储最终答案，初始值为无穷大 63 64 65 for(k=1;k<=m;k++)//枚举各列为第一列 66 { 67 for(i=1;i<=n;i++) 68 for(j=1;j<=m;j++) 69 temp[i][j]=a[i][j]; 70 need=0; 71 ChangeL(1,k); 72 73 74 //不满足的行，进行一次变换 75 for(i=1;i<=n;i++) 76 { 77 if(temp[i][1]!=b[i][1])//该行不满足条件 78 { 79 ChangeH(i);//变换行 80 need++; 81 } 82 } 83 84 85 bool find; 86 for(i=1;i<=m;i++)//检查每列是否满足条件 87 { 88 find=false; 89 if(Same(i,i)) 90 { 91 find=true; 92 continue; 93 } 94 for(j=i+1;j<=m;j++)//寻找temp中与b的i列相同的列 95 { 96 if(Same(i,j))//temp 的 j列于b的i列相同 97 { 98 if(Same(j,j))continue;//temp的j列与b的j列相同 99 ChangeL(i,j);//交换temp的i，j列 100 find=true; 101 break; 102 } 103 } 104 if(find==false)//找不到该列对应列 105 { 106 break; 107 } 108 } 109 110 111 if(find==true&&need<ans) 112 ans=need; 113 } 114 115 116 if(ans<inf) 117 printf("%d\n",ans); 118 else 119 printf("-1\n"); 120 } 121 return 0; 122 }
参考资料：http://blog.csdn.net/sftxlin/article/details/7282645
