程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C >> C語言基礎知識 >> c語言:金幣陣列的問題

c語言:金幣陣列的問題

編輯:C語言基礎知識

  有m*n(m <=100,n <=100)個金幣在桌面上排成一個m行n 列的金幣陣列。每一枚金幣或正面朝上或背面朝上。用數字表示金幣狀態,0表示金幣正面朝上,1 表示背面朝上。

  金幣陣列游戲的規則是: (1)每次可將任一行金幣翻過來放在原來的位置上;

  (2)每次可任選2 列,交換這2 列金幣的位置。

   編程任務:給定金幣陣列的初始狀態和目標狀態,編程計算按金幣游戲規則,將金幣陣列從初始狀態變換到目標狀態所需的最少變換次數。

Input

  輸入數據有多組數據。第1行有1 個正整數k,表示有k 組數據。每組數據的第1 行有2 個正整數m 和n。以下的m行是金幣陣列的初始狀態,每行有n 個數字表示該行金幣的狀態,0 表示金幣正面朝上,1 表示背面朝上。接著的m行是金幣陣列的目標狀態。

Output

  將計算出的最少變換次數按照輸入數據的次序輸出。相應數據無解時輸出-1。

代碼是別人的,感覺寫的很好。寫這個博客,主要是想要重溫一下思路。

枚舉1~m中,每一列為第一列的情況,

//從1~n行,找出不滿足的行,進行一次行變換

//若是所枚舉的這一列可以成功根據規則轉換成目標矩陣,則,此時的矩陣與原矩陣的差別只會在列序上

此時,從i=2 列(第二列)開始與目標矩陣的第i列進行比較,

若不同,尋找本矩陣中第j列(就= i+1~m)是否有與目標矩陣的第i列相同的,若有,且 本矩陣第j列!= 目標矩陣第j列,則,進行一次列變換

//若是找不到符合條件的列,則所枚舉的這一列為第一列是不可能按所給規則變換到目標矩陣的

代碼如下:

#include<stdio.h>

 const int inf = 99999;
 const int N = 101;

 int a[N][N],b[N][N],temp[N][N]; //a存儲初始矩陣,b為目標狀態矩陣
 int n,m;
 int need;//需要變換次數

 void ChangeL(int x,int y)//變換列
 {
     if(x==y)return;
     int i;
     for(i=1;i<=n;i++)
     {
         int tt=temp[i][y];
         temp[i][y]=temp[i][x];
         temp[i][x]=tt;
     }
     need++;
 }

 void ChangeH(int x)//變換行
 {
     int i;
     for(i=1;i<=m;i++)
     {
         temp[x][i]^=1;
     }
 }

 bool Same(int x,int y) //判斷列是否滿足條件
 {
     int i;
     for(i=1;i<=n;i++)
         if(b[i][x]!=temp[i][y])return false;
     return true;
 }

 int main()
 {
     int tests;
     scanf("%d",&tests); //數據組數

     while(tests--)
     {
         scanf("%d%d",&n,&m); //n行,m列
         int i,j;
         for(i=1;i<=n;i++)
             for(j=1;j<=m;j++)
             {
                 scanf("%d",&a[i][j]);
             }

             for(i=1;i<=n;i++)
                 for(j=1;j<=m;j++)
                     scanf("%d",&b[i][j]);

             int k;
             int ans=inf; //ans存儲最終答案,初始值為無窮大

 
             for(k=1;k<=m;k++)//枚舉各列為第一列
             {
                 for(i=1;i<=n;i++)
                     for(j=1;j<=m;j++)
                         temp[i][j]=a[i][j];
                 need=0;
                 ChangeL(1,k);

 
                 //不滿足的行,進行一次變換
                 for(i=1;i<=n;i++)
                 {
                     if(temp[i][1]!=b[i][1])//該行不滿足條件
                     {
                         ChangeH(i);//變換行
                         need++;
                     }
                 }

                 bool find;
                 for(i=1;i<=m;i++)//檢查每列是否滿足條件
                 {
                     find=false;
                     if(Same(i,i))
                     {
                         find=true;
                         continue;
                     }
                     for(j=i+1;j<=m;j++)//尋找temp中與b的i列相同的列
                     {
                         if(Same(i,j))//temp 的 j列於b的i列相同
                         {
                             if(Same(j,j))continue;//temp的j列與b的j列相同
                             ChangeL(i,j);//交換temp的i,j列
                             find=true;
                             break;
                         }
                     }
                     if(find==false)//找不到該列對應列
                     {
                         break;
                     }
                 }

                 if(find==true&&need<ans)
                     ans=need;
             }

             if(ans<inf)
                 printf("%d\n",ans);
             else
                 printf("-1\n");
     }
     return 0;
 }

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved