算法分析题——金币列阵问题（C实现）

心已赠人 2024-03-26 19:42 61阅读 0赞

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

金币阵列的游戏规则是：（1）一次可将任意一行金币翻过来放在原来的位置上；（2）每次可任选2列。交换这2列金币的位置。

**算法设计**：给定金币阵列的初始状态和目标状态，计算按金币游戏规则，将金币从初始状态变换到目标状态所需的最少变换次数

**数据输入：**由文件input.txt给出输入数据。文件中有多组数据。文件的第1行有有1个正整数k，表示有k组数据。每一组数据的第1行有2个正整数m和n。以下m是金币阵列的初始状态，每行有n数字表示该行金币状态，0表示正面朝上，1表示背面朝上。接着的m行是金币阵列的目标转状态。

**输出结果**：将计算出的最少变换次数按照输入数据的次序输入到文件output.txt。相应数据无解时，输出-1。

#include<stdio.h> 
    #define size 200
    
        int num; //读入有几组数据 
        int row,column; //行数与列数 
        int count; //交换次数
        int min;
        int a[size][size]; //目标矩阵
        int b[size][size]; //初始矩阵
        int c[size][size]; //临时存放矩阵
        int found; //初始到最终是否有交换
    
    //金币阵列的规则 
    void trans_row(int x) // 第x行取反 
    {
        int i;
        for (i = 0;i<column; i++) 
            b[x][i] = b[x][i]^1; // 异进行或取反 
        count++;
    }
    
    int trans_column(int x, int y) // x和y列进行交换 
    {
        int i;
        int temp;
        for(i = 0; i < row; i++)
        {
            temp=b[i][x];
            b[i][x]=b[i][y];
            b[i][y]=temp;
        }
        if (x != y) 
            count++;
    }
    
    int is_same(int x, int y) //比较x和y列是否相同 
    {
        int i;
        for(i = 0; i <row; i++)
            if (a[i][x] != b[i][y])
                return 0;//如果两列不相同返回0 
        return 1;//如果相同返回1 
    }
    
    void copy(int a[size][size], int b[size][size]) // 拷贝数组 
    {
        int i,j;
        for (i = 0; i <row; i++)
            for (j = 0; j < column; j++)
                a[i][j] = b[i][j];
    }
    
    int main()
    {
    
        int i,j,k,p;
        int exchgmin[size];
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
        
        scanf("%d",&num);
        for(i=0;i<num;i++)
        {
            scanf("%d",&row);
            scanf("%d",&column);
            for(j=0;j<row;j++)
                for(k=0;k<column;k++)
                    scanf("%d",&a[j][k]);
            for(j=0;j<row;j++)
                for(k=0;k<column;k++)
                    scanf("%d",&b[j][k]);
                            
            copy(c,b); //保护初始矩阵b 
            min=row+column+1;
            
            for(j=0;j<column;j++)
            {
                copy(b,c); //恢复初始数组b 
                count=0;  //交换次数清零 
                trans_column(0,j); //把每一列都假设成为第一列的目标状态，穷举这column中情况 
                for(k=0;k<row;k++)
                { //如果行不同，则将行转换 
                    if(a[k][0]!=b[k][0])
                    trans_row(k);
                }
                int lo[200],flag=0,tot=0;
                for(k=1;k<column;k++)
                {//穷举其他所有列，如果相同则交换，说明目标状态统一，否则找不到与该列相同，说明不可行 
                    found=0;//记录是否找到相同列 
                    tot=0;flag=0;//flag记录是否有交换后都相同的列 
                    for(p=k;p<column;p++)
                    {
                        if(is_same(k,p))
                        {
                            found=1;
                            if(p==k)
                                {break;}
                            lo[tot++]=p;
                            if(is_same(p,k))//此步实现优先选择列一致的 
                                {flag=1;trans_column(k,p);break;}
                        }
                    }
                    if(!found)
                        break;
                    else if(!flag && tot)//没有交换后两列都符合的，则与第一次发现的列交换 
                        trans_column(k,lo[0]);
                }
                if(found&&count<min) //如果可行，找出最小值 
                    min=count; 
            }
            if(min<row+column+1) //如果交换次数比初始值小，将其保存为当前组的最小交换次数，否则不可实现交换 
                exchgmin[i]=min;
            else exchgmin[i]=-1;
        }
        for(i=0;i<num;i++)
        printf("%d\n",exchgmin[i]);
        return 0;
    }

那么现在来检验一下结果吧~

（1）现在程序路径下建立题目所需的两个文件

![60f49468a5ed4a61bd7a67ca9be2d67d.png][]

（2）在文本文件intput.txt中输入需要检验的内容

![591e70c907cc4e5b8114b7f324d64ff6.png][]

（3）然后可以开始运行程序了

![05156253f0be4c0881e9fe0c84739a02.png][]

（4）程序运行成功后，打开output.txt文件进行检验

![c588f023e938453fa66dd99cd7ce41f5.png][]

这样整个程序就检验完毕啦~

[60f49468a5ed4a61bd7a67ca9be2d67d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ed295e23f2094f72b508b29a2a451aea.png
[591e70c907cc4e5b8114b7f324d64ff6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/4f04b869a87c45a7b0caf48145c4562d.png
[05156253f0be4c0881e9fe0c84739a02.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/12b0176a3e1b406bba1d13ac69077bcb.png
[c588f023e938453fa66dd99cd7ce41f5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/a37698c196304f2288e92b65f96304bc.png