題目描述：
金幣陣列問題。
有m*n枚金幣在桌面上排成一個(gè)金幣陣列。每一個(gè)金幣正面朝上，或背面朝上蕉汪，分別用0和1表示。 金幣陣列游戲的規(guī)則是：（1）每次可將任一行金幣翻過來放在原來的位置上逞怨；（2）每次可任選2列者疤，交換這2列金幣的位置。
給定金幣的初始狀態(tài)和目標(biāo)狀態(tài)叠赦，計(jì)算按金幣游戲規(guī)則驹马，將金幣陣列從初始狀態(tài)變換到目標(biāo)狀態(tài)所需的最少變換次數(shù)。
示例：
一種正確思路
預(yù)先設(shè)定兩個(gè)數(shù)組眯搭，coin1和coin2,當(dāng)然也可以自行輸入
再設(shè)定一個(gè)替身數(shù)組窥翩，temparr
保證coin2數(shù)組在整個(gè)過程中不能被改變，coin1原數(shù)組也不能改變鳞仙，但是可以把coin1賦值給temparr,來改變temparr的值
以coin2的0號(hào)列為標(biāo)桿寇蚊，讓temparr的0號(hào)列與它比較，如果coin2[i][0]!=temparr[i][0]棍好，就把i這一行都翻轉(zhuǎn)仗岸，知道0號(hào)列的最后一個(gè)數(shù)字。
到這里借笙，coin2和temparr的0號(hào)列就相同了扒怖，同時(shí)也被固定下來，后面不能再改變业稼。所以盗痒，后續(xù)的列就不能在整行地翻轉(zhuǎn)，因?yàn)檫@樣會(huì)改變0號(hào)列。后續(xù)的列只能通過交換位置的方式變成目標(biāo)陣列俯邓。
如果后續(xù)的列交換位置后骡楼，元素都能和目標(biāo)陣列匹配，則證明最初拿temparr0號(hào)列與coin2的0號(hào)列比較的決定是正確地稽鞭，此時(shí)輸出交換的次數(shù)即可鸟整。
如果后續(xù)的列和目標(biāo)陣列不匹配，則證明最初拿temparr0號(hào)列與coin2的0號(hào)列比較的決定是錯(cuò)誤的朦蕴。應(yīng)該讓coin1給temparr重新賦值篮条，再讓temparr的1號(hào)列進(jìn)行此過程，看能否行得通吩抓。如果再不行涉茧，就temparr的2號(hào)列......如此循環(huán)，直到temparr的最后一列疹娶。
假如temparr的列都不行降瞳，則證明coin1根本不可能轉(zhuǎn)換到coin2，輸出“無法轉(zhuǎn)換”蚓胸，結(jié)束程序。
代碼：
#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; //轉(zhuǎn)換的次數(shù)
int minnum=9999;
void trans1(int i) //第i行翻轉(zhuǎn)
{
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的列
{
//給替身數(shù)組賦值
for(j=0;j<row;j++)
{
for(k=0;k<col;k++)
{
temparr[j][k]=coin1[j][k];
}
}
number=0;
trans2(0,i); //temparr數(shù)組的列先做交換沛膳，把其他列放到第一列的位置
for(j=0;j<row;j++) //判斷temparr的0號(hào)列和coin2的0號(hào)列是否相同，不同則翻轉(zhuǎn)
{
if(temparr[j][0]!=coin2[j][0])
{
trans1(j); //如果第1列不匹配汛聚，那么行全部翻轉(zhuǎn)
}
}
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("次數(shù)為：%d\n",minnum);
return 0;
}else{
printf("No！\n");
return 0;
}
return 0;
}
當(dāng)前數(shù)組下痕貌，轉(zhuǎn)換次數(shù)為5次
覺得正確但是錯(cuò)誤的一種思路：
從0號(hào)行開始判斷风罩，如果coin1和coin2的某一行的1的個(gè)數(shù)相加等于col的大小，則翻轉(zhuǎn)
如果coin1某一行的1的個(gè)數(shù)舵稠，等于coin2的某一行的1的個(gè)數(shù)超升，則不需要翻轉(zhuǎn)
如果coin1和coin2的某一行的1的個(gè)數(shù)既不相等，相加也不等于col的大小哺徊，則無法翻轉(zhuǎn)
此種分析看似合理室琢，代碼也能寫出來，但是col為偶數(shù)時(shí)落追，此程序會(huì)混亂盈滴，col為奇數(shù)，則能正常執(zhí)行
下面是此種情況的代碼：
#include<stdio.h>
#define row 4
#define col 3
int main(){
int number=0;//記錄轉(zhuǎn)換的次數(shù)
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("目標(biāo)初始金幣陣列(%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;
//先對(duì)行操作
for(i=0;i<row&&flag;i++){
sum1=sum2=0;
for(j=0;j<col;j++){ //求某一行1的個(gè)數(shù)
sum1+=coin1[i][j];
sum2+=coin2[i][j];
}
if(sum1+sum2==col){ //需要某一行翻轉(zhuǎn)的情況
flag=1;
number++;
for(k=0;k<col;k++){
coin1[i][k]=(1-coin1[i][k]);
}
}else if(sum1==sum2){ //不需要翻轉(zhuǎn)
flag=1;
}
else{ //不能翻轉(zhuǎn)的情況
flag=0;
}
}
int flag1;
if(flag==1){ //flag為1巢钓，證明能轉(zhuǎn)換
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){//找到匹配病苗，進(jìn)行列交換
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("轉(zhuǎn)換%d次\n",number);
return 0;
}
break;
}
}
}else{ //flag不為1，證明不能轉(zhuǎn)換
printf("不能轉(zhuǎn)換竿报！\n");
return 0;
}
return 0;
}
