C语言金币阵列问题解决方法
本文实例详细讲述了C语言实现金币阵列问题的解决方法,分享给大家供大家参考。具体方法如下:
问题描述:
有m*n(1≤m,n≤100)个金币在桌面上排成一个m行n列的阵列。每一枚金币或正面朝上或背面朝上。用数字表示金币状态,0表示金币正面朝上,1表示背面朝上。
金币阵列游戏的规则是:
1.每次可将任一行金币翻过来放在原来的位置上;
2.每次可任选2列,交换这2列金币的位置。
本题要求对于给定的金币阵列初始状态和目标状态,编程计算按金币游戏规则,将金币阵列从初始状态变换到目标状态所需的最少变换次数。
数据输入:
输入的测试数据的第一行是一个不超过10的正整数k,表示有k个测试用例.每个测试用例的第一行是两个正整数m,n.接下来是m行,每行有n个用空白符分隔的0或1.这m*n个0-1表示金币的初始状态阵列。最后是m行,每行n个用空白符分隔的0或1,表示金币阵列的目标状态。
数据输出:
对于每个测试用例,输出一行包含一个整数,表示按照要求规则将金币阵列从初始状态变换为目标状态所需要的最少变换次数。如果不能按照变换规则将初始状态变换为目标状态(即无解时)则输出-1。
数据样例:
SampleInput
2
43
101
000
110
101
101
111
011
101
43
101
000
100
111
110
111
011
101
SampleOutput
2
-1
C语言实现代码如下:
#include"stdio.h" #include"stdlib.h" #definesize100 intnum;//输入几组数据 introw;//行数 intcolumn;//列数 intcount;//交换次数 intmin; inta[size][size];//初始矩阵 intb[size][size];//最终矩阵 intc[size][size];//临时存放矩阵 intfound;//初始到最终是否有交换 voidtrans_row(intx)//第x行取反 { inti; for(i=0;i<column;i++) b[x][i]=b[x][i]^1;//异或取反 count++; } voidtrans_column(intx,inty)//交换x和y列 { inti; inttemp; for(i=0;i<row;i++){ temp=b[i][x]; b[i][x]=b[i][y]; b[i][y]=temp; } if(x!=y) count++; } intis_same(intx,inty)//比较x和y列是否相同 { inti; for(i=0;i<row;i++) if(a[i][x]!=b[i][y]) return0; return1; } voidcopy(inta[size][size],intb[size][size])//拷贝数组 { inti,j; for(i=0;i<row;i++) for(j=0;j<column;j++) a[i][j]=b[i][j]; } intmain(){ inti,j,k,p; intexchgmin[size]; 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); } for(k=0;k<column;k++){//穷举其他所有列,如果相同则交换,说明目标状态统一,否则找不到与该列相同,说明不可行 found=0; for(p=k;p<column;p++){ if(is_same(k,p)){ trans_column(k,p); found=1; break; } } if(!found) break; } if(found&&count<min)//如果可行,找出最小值 min=count; } if(min<row+column+1)//如果交换次数比初始值小,将其保存为当前组的最小交换次数,否则不可实现交换 exchgmin[i]=min; elseexchgmin[i]=-1; } for(i=0;i<num;i++) printf("%d/n",exchgmin[i]); system("pause"); return0; }
希望本文所述对大家C程序算法设计的学习有所帮助。