题目描述：
金币阵列问题。
有m*n枚金币在桌面上排成一个金币阵列。每一个金币正面朝上，或背面朝上，分别用0和1表示。 金币阵列游戏的规则是：（1）每次可将任一行金币翻过来放在原来的位置上；（2）每次可任选2列，交换这2列金币的位置。
给定金币的初始状态和目标状态，计算按金币游戏规则，将金币阵列从初始状态变换到目标状态所需的最少变换次数。
示例：
一种正确思路
预先设定两个数组，coin1和coin2,当然也可以自行输入
再设定一个替身数组，temparr
保证coin2数组在整个过程中不能被改变，coin1原数组也不能改变，但是可以把coin1赋值给temparr,来改变temparr的值
以coin2的0号列为标杆，让temparr的0号列与它比较，如果coin2[i][0]!=temparr[i][0]，就把i这一行都翻转，知道0号列的最后一个数字。
到这里，coin2和temparr的0号列就相同了，同时也被固定下来，后面不能再改变。所以，后续的列就不能在整行地翻转，因为这样会改变0号列。后续的列只能通过交换位置的方式变成目标阵列。
如果后续的列交换位置后，元素都能和目标阵列匹配，则证明最初拿temparr0号列与coin2的0号列比较的决定是正确地，此时输出交换的次数即可。
如果后续的列和目标阵列不匹配，则证明最初拿temparr0号列与coin2的0号列比较的决定是错误的。应该让coin1给temparr重新赋值，再让temparr的1号列进行此过程，看能否行得通。如果再不行，就temparr的2号列......如此循环，直到temparr的最后一列。
假如temparr的列都不行，则证明coin1根本不可能转换到coin2，输出“无法转换”，结束程序。
代码：
#include<stdio.h>
#define row 4
#define col 3
int coin1[row][col]={{1,0,1},{0,1,0},{1,1,0},{1,0,1}}; //source
int coin2[row][col]={{0,0,1},{1,1,0},{1,0,0},{1,1,0}}; //target ，不可被修改
int temparr[row][col];
int number=0; //转换的次数
int minnum=9999;
void trans1(int i) //第i行翻转
{
int j;
for(j=0;j<col;j++)
{
temparr[i][j]=1-temparr[i][j];
}
number++;
}
void trans2(int i,int j) //第i列与第j列互换
{
int temp,k;
for(k=0;k<row;k++)
{
temp=temparr[k][i];
temparr[k][i]=temparr[k][j];
temparr[k][j]=temp;
}
if(i!=j)
number++;
}
int judge(int i,int j) //temparr的i列是否和coin2的j列相同
{
int flag;
for(int k=0;k<row;k++)
{
flag=1;
if(temparr[k][i]!=coin2[k][j])
{
flag=0;
break;
}
}
return flag;
}
int main()
{
int i,j,k;
for(i=0;i<col;i++) //代表coin1的列
{
//给替身数组赋值
for(j=0;j<row;j++)
{
for(k=0;k<col;k++)
{
temparr[j][k]=coin1[j][k];
}
}
number=0;
trans2(0,i); //temparr数组的列先做交换，把其他列放到第一列的位置
for(j=0;j<row;j++) //判断temparr的0号列和coin2的0号列是否相同，不同则翻转
{
if(temparr[j][0]!=coin2[j][0])
{
trans1(j); //如果第1列不匹配，那么行全部翻转
}
}
int found;
for(j=0;j<col;j++) //代表coin2，从第2行开始，到最后一行
{
found=0;
for(k=j;k<col;k++) //代表temparr，从第2行开始，直到最后一行
{
if(judge(k,j))
{
found=1;
trans2(k,j);
break;
}
}
if(!found)
{
break;
}
}
if(found)
{
minnum=number;
}
}
if(minnum<9999)
{
printf("次数为：%d\n",minnum);
return 0;
}else{
printf("No！\n");
return 0;
}
return 0;
}
当前数组下，转换次数为5次
觉得正确但是错误的一种思路：
从0号行开始判断，如果coin1和coin2的某一行的1的个数相加等于col的大小，则翻转
如果coin1某一行的1的个数，等于coin2的某一行的1的个数，则不需要翻转
如果coin1和coin2的某一行的1的个数既不相等，相加也不等于col的大小，则无法翻转
此种分析看似合理，代码也能写出来，但是col为偶数时，此程序会混乱，col为奇数，则能正常执行
下面是此种情况的代码：
#include<stdio.h>
#define row 4
#define col 3
int main(){
int number=0;//记录转换的次数
int i,j,k;
/*
int coin1[row][col];
int coin2[row][col];
printf("输入初始金币阵列(%d行%d列)：\n",row,col);
for(i=0;i<row;i++){
for(j=0;j<col;j++){
scanf("%d",&coin1[i][j]);
}
}
printf("目标初始金币阵列(%d行%d列)：\n",row,col);
for(i=0;i<row;i++){
for(j=0;j<col;j++){
scanf("%d",&coin2[i][j]);
}
}
*/
int coin1[4][3]={{1,0,1},{0,1,0},{1,1,0},{1,0,1}}; //source
int coin2[4][3]={{0,0,1},{1,1,0},{1,0,0},{1,1,0}}; //target ，不可被修改
int sum1=0,sum2=0,flag=1;
//先对行操作
for(i=0;i<row&&flag;i++){
sum1=sum2=0;
for(j=0;j<col;j++){ //求某一行1的个数
sum1+=coin1[i][j];
sum2+=coin2[i][j];
}
if(sum1+sum2==col){ //需要某一行翻转的情况
flag=1;
number++;
for(k=0;k<col;k++){
coin1[i][k]=(1-coin1[i][k]);
}
}else if(sum1==sum2){ //不需要翻转
flag=1;
}
else{ //不能翻转的情况
flag=0;
}
}
int flag1;
if(flag==1){ //flag为1，证明能转换
for(i=0;i<col;i++){ //控制coin2的列
for(j=i;j<col;j++){ //控制coin1的列
for(k=0;k<row;k++){ //控制coin1和coin2的行
flag1=1;
if(coin2[k][i]!=coin1[k][j]){
flag1=0; //flag1==0,证明没有成功匹配
break;
}
}
if(!flag1){
continue;
}
if(flag1){//找到匹配，进行列交换
for(k=0;k<row;k++){
int temp;
temp=coin1[k][j];
coin1[k][j]=coin1[k][i];
coin1[k][i]=temp;
}
number++;
}
int flag2=1;
for(int a=0;a<row;a++){
for(int b=0;b<col;b++){
if(coin1[a][b]!=coin2[a][b])
{
flag2=0;
}
}
}
if(flag2){
printf("转换%d次\n",number);
return 0;
}
break;
}
}
}else{ //flag不为1，证明不能转换
printf("不能转换！\n");
return 0;
}
return 0;
}
