金币阵列问题

---

---

题目描述：

金币阵列问题。
有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;
}

---

---