金币阵列问题

 

  有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

 

上一篇:几个问题的思考


下一篇:.NET 使用OpenSSL生成的pem文件做为RSA Key时的读取问题