金币阵列

偏执的太偏执、 2022-08-02 12:39 250阅读 0赞

问题描述：有m\*n枚金币在桌面上排列成一个m行n列的金币阵列。每一枚金币或正面朝上，或背面朝上。用数字表示金币状态，0表示正面朝上，1表示背面朝上。

金币阵列游戏的规则是：

（1）每次将任一行金币翻过来放在原来的位置上。

（2）每次可以任选2列，交换这2列金币的位置。

任务：给定金币的初始状态和目标状态，编程计算按金币游戏规则，将金币排列从初始状态变换到目标状态所需的最少变换次数。

解题思路：

本例的实质是将一个二进制矩阵从一种形式利用相应规则变换到另一种形式。提供的规则有两种：

（1）将某一行的金币翻转；

（2）将某两列进行交换。

在这两种操作中，第一种操作可能会影响到某一行或者某一列中已经排列好的相关元素，因此，首先利用该规则进行变换，而后续的操作则不再利用该规则。算法的具体思路如下：

（1）将矩阵中的每一列作为第1列，并利用第一个规则将第1列中的相关元素与目标矩阵中第1列的元素进行配对，如果不相同，则利用每1个规则进行翻转；

（2）从第2列开始，将处理后的列与目标列进行比较，如果相同，则转下一列；如果不相同，看是否可以通过列的交换完成，如果不可以，则无法做到，如果可以，则继续扫描，直至所有的列描述完成为止。

参考代码：

#include <stdio.h>
     
    inta[4][3]={
       {1,0,1},{0,0,0},{1,1,0},{1,0,1}}; //source
    intb[4][3]={
       {1,0,1},{1,1,1},{0,1,1},{1,0,1}}; //target
    int temparr[4][3];
    int m=4, n=3;
    int count;
     
    void main()
    {
        voidtrans1(int);       //对某一行进行翻转
        voidtrans2(int, int);  //对某两列进行互换
        boolsame(int, int);    //判断temparr中的列和b中的列是否相同
       
        inti,j,k;
       
        int answer=9999;
     
    //整体思路，将每一列运用列交换作为第1列，然后对每一行进行判断，如果元素//与目标元素不相等，
     
    //进行翻转处理，再向后判断相关列是否相同。
        for(k=0;k<m;k++)
        {
            //copyarray
            for(i=0;i<m;i++)   
                for(j=1;j<n;j++)
                    temparr[i][j]=a[i][j];
           
            count=0;
            trans2(1,k);//将第k列与第1列互换
     
           
            //对所有行的第1个元素与目标数组对应的元素进行比较，如果不同
            //进行按行变换
            for(i=0;i<m;i++)
            {
                if(temparr[i][0]!=b[i][0])
                    trans1(i); 
            }
           
     
            //检查每一列是否满足条件
            boolfound;
            for(i=0;i<n;i++)
            {
                found=false;
                if(same(i,i))
                {
                    found=true;continue;
                }
     
                for(j=i+1;j<n;j++)//判断是否可以通过后续列的交换达到目的
                {
                    if(same(i,j))
                    {
                        trans2(i,j);
                        found=true;
                        break;
                    }
                }
     
                if(found==false)
                    break;
            }
     
            if(found==true) answer=count;
        }
        if(answer<9999)
            printf("yes.the steps needed is %d.\n",count);
        else
            printf("no.\n");
     
    }
     
    void trans1(int j)
    //对某一行进行翻转
    {
        for(inti=0;i<3;i++)
            temparr[j][i]=1-temparr[j][i];// a[j][i]^=1; //异或运算也可以
     
        count++;
    }
     
     
    void trans2(int i,int j)
    //对两列进行互换
    {
        for(intk=0;k<4;k++)
        {
            inttemp=temparr[k][i];
            temparr[k][i]=temparr[k][j];
            temparr[k][j]=temp;
        }
     
        if(i!=j) count++;
    }
     
     
    bool same(int j,int i)
    //判断两列是否相同
    {
        intk;
        boolflag=true;
     
        for(k=0;k<m;k++)
        {
            if(temparr[k][i]!=b[k][j])
            {
                flag=false;
                break;
            }
        }
        returnflag;
    }