C語言金幣陣列問題解決方法
本文實(shí)例詳細(xì)講述了C語言實(shí)現(xiàn)金幣陣列問題的解決方法,分享給大家供大家參考。具體方法如下:
問題描述:
有m*n(1 ≤ m, n ≤ 100)個(gè)金幣在桌面上排成一個(gè) m 行 n 列的陣列。每一枚金幣或正面朝上或背面朝上。用數(shù)字表示金幣狀態(tài),0表示金幣正面朝上,1 表示背面朝上。
金幣陣列游戲的規(guī)則是:
1. 每次可將任一行金幣翻過來放在原來的位置上;
2. 每次可任選 2 列,交換這 2 列金幣的位置。
本題要求對于給定的金幣陣列初始狀態(tài)和目標(biāo)狀態(tài),編程計(jì)算按金幣游戲規(guī)則,將金幣陣列從初始狀態(tài)變換到目標(biāo)狀態(tài)所需的最少變換次數(shù)。
數(shù)據(jù)輸入:
輸入的測試數(shù)據(jù)的第一行是一個(gè)不超過 10 的正整數(shù) k,表示有 k 個(gè)測試用例. 每個(gè)測試用例的第一行是兩個(gè)正整數(shù) m, n. 接下來是 m 行,每行有 n 個(gè)用空白符分隔的 0 或 1. 這 m*n 個(gè) 0-1 表示金幣的初始狀態(tài)陣列。最后是 m 行,每行 n 個(gè) 用空白符分隔的 0 或 1,表示金幣陣列的目標(biāo)狀態(tài)。
數(shù)據(jù)輸出:
對于每個(gè)測試用例,輸出一行包含一個(gè)整數(shù),表示按照要求規(guī)則將金幣陣列從初始狀態(tài)變換為目標(biāo)狀態(tài)所需要的最少變換次數(shù)。如果不能按照變換規(guī)則將初始狀態(tài)變換為目標(biāo)狀態(tài)(即無解時(shí))則輸出 -1。
數(shù)據(jù)樣例:
Sample Input
2
4 3
1 0 1
0 0 0
1 1 0
1 0 1
1 0 1
1 1 1
0 1 1
1 0 1
4 3
1 0 1
0 0 0
1 0 0
1 1 1
1 1 0
1 1 1
0 1 1
1 0 1
Sample Output
2
-1
C語言實(shí)現(xiàn)代碼如下:
#include "stdio.h" #include "stdlib.h" #define size 100 int num; //輸入幾組數(shù)據(jù) int row; //行數(shù) int column; //列數(shù) int count; //交換次數(shù) int min; int a[size][size]; //初始矩陣 int b[size][size]; //最終矩陣 int c[size][size]; //臨時(shí)存放矩陣 int found; //初始到最終是否有交換 void trans_row(int x) // 第x行取反 { int i; for (i = 0;i<column; i++) b[x][i] = b[x][i]^1; // 異或取反 count++; } void 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; return 1; } void copy(int a[size][size], int b[size][size]) // 拷貝數(shù)組 { 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]; 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); //保護(hù)原始數(shù)組b min=row+column+1; for(j=0;j<column;j++){ copy(b,c); //恢復(fù)原始數(shù)組b count=0; //交換次數(shù)清零 trans_column(0,j); //把每一列都假設(shè)成為第一列的目標(biāo)狀態(tài),窮舉這column中情況 for(k=0;k<row;k++){ //如果行不同,則將行轉(zhuǎn)換 if(a[k][0]!=b[k][0]) trans_row(k); } for(k=0;k<column;k++){//窮舉其他所有列,如果相同則交換,說明目標(biāo)狀態(tài)統(tǒng)一,否則找不到與該列相同,說明不可行 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) //如果交換次數(shù)比初始值小,將其保存為當(dāng)前組的最小交換次數(shù),否則不可實(shí)現(xiàn)交換 exchgmin[i]=min; else exchgmin[i]=-1; } for(i=0;i<num;i++) printf("%d/n",exchgmin[i]); system("pause"); return 0; }
希望本文所述對大家C程序算法設(shè)計(jì)的學(xué)習(xí)有所幫助。
上一篇:C語言實(shí)現(xiàn)找出二叉樹中某個(gè)值的所有路徑的方法
欄 目:C語言
下一篇:C語言實(shí)現(xiàn)圖的遍歷之深度優(yōu)先搜索實(shí)例
本文標(biāo)題:C語言金幣陣列問題解決方法
本文地址:http://mengdiqiu.com.cn/a1/Cyuyan/3363.html
您可能感興趣的文章
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用函數(shù)刪除字符
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)式函數(shù)庫
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言中對數(shù)函數(shù)的表達(dá)式 c語言中對數(shù)怎么表達(dá)
- 04-02c語言用函數(shù)寫分段 用c語言表示分段函數(shù)
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排序法函數(shù)
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段函數(shù)
- 04-02C語言中怎么打出三角函數(shù) c語言中怎么打出三角函數(shù)的值
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求階乘


閱讀排行
本欄相關(guān)
- 04-02c語言函數(shù)調(diào)用后清空內(nèi)存 c語言調(diào)用
- 04-02func函數(shù)+在C語言 func函數(shù)在c語言中
- 04-02c語言的正則匹配函數(shù) c語言正則表達(dá)
- 04-02c語言用函數(shù)寫分段 用c語言表示分段
- 04-02c語言中對數(shù)函數(shù)的表達(dá)式 c語言中對
- 04-02c語言編寫函數(shù)冒泡排序 c語言冒泡排
- 04-02c語言沒有round函數(shù) round c語言
- 04-02c語言分段函數(shù)怎么求 用c語言求分段
- 04-02C語言中怎么打出三角函數(shù) c語言中怎
- 04-02c語言調(diào)用函數(shù)求fibo C語言調(diào)用函數(shù)求
隨機(jī)閱讀
- 01-10C#中split用法實(shí)例總結(jié)
- 01-10delphi制作wav文件的方法
- 08-05DEDE織夢data目錄下的sessions文件夾有什
- 01-10SublimeText編譯C開發(fā)環(huán)境設(shè)置
- 08-05dedecms(織夢)副欄目數(shù)量限制代碼修改
- 01-10使用C語言求解撲克牌的順子及n個(gè)骰子
- 08-05織夢dedecms什么時(shí)候用欄目交叉功能?
- 01-11ajax實(shí)現(xiàn)頁面的局部加載
- 04-02jquery與jsp,用jquery
- 01-11Mac OSX 打開原生自帶讀寫NTFS功能(圖文