C语言金币阵列难点一蹴即至方法

发布时间:2019-05-18  栏目:sqlite  评论:0 Comments

本文实例详细描述了C语言完毕金币阵列难题的缓慢解决措施,分享给我们供大家参照他事他说加以调查。具体方法如下:

 

难题讲述:

  有m*n(m <=拾0,n <=拾0)个金币在桌面上排成二个m行n
列的金币阵列。每1枚金币或正面朝上或背面朝上。用数字代表金币状态,0代表金币正面朝上,一代表背面朝上。

有m*n(一 ≤ m, n ≤ 100)个金币在桌面上排成一个 m 行 n
列的阵列。每壹枚金币或正面朝上或背面朝上。用数字代表金币状态,0代表金币正面朝上,1表示背面朝上。

  金币阵列游戏的平整是:
(一)每回可将任一行金币翻过来放在原位上;

金币阵列游戏的平整是:

  (二)每回可任选二 列,交流那贰 列金币的职责。

  1. 老是可将任一行金币翻过来放在原来的职位上;
  2. 历次可任选 贰 列,调换那 二 列金币的岗位。
    核心供给对于给定的金币阵列起初状态和目的状态,编制程序总结按金币游戏规则,将金币阵列从开头状态转换来目的状态所需的最少改换次数。

  
编程职责:给定金币阵列的开始状态和对象状态,编程总括按金币游戏规则,将金币阵列从开端状态转变成对象状态所需的最少退换次数。

数量输入:

 

输入的测试数据的第二行是二个不当先 10 的正整数 k,表示有 k 个测试用例.
每一种测试用例的第3行是七个正整数 m, n. 接下去是 m 行,每行有 n
个用空白符分隔的 0 或 1. 那 m*n 个 0-一 表示金币的始发状态阵列。最终是
m 行,每行 n 个 用空白符分隔的 0 或 壹,表示金币阵列的指标状态。

Input

多少输出:

  输入数据有多组数据。第3行有一 个正整数k,表示有k
组数据。每组数据的第三 行有二 个正整数m
和n。以下的m行是金币阵列的始发状态,每行有n 个数字代表该行金币的境况,0
代表金币正面朝上,一 表示背面朝上。接着的m行是金币阵列的指标状态。

对于各类测试用例,输出1行包涵1个平头,表示遵照须要规则将金币阵列从先导状态转变为对象状态所需求的最少更动次数。假如不可能依照转换规则将上马状态转换为目的状态(即无解时)则输出
-一。

 

数码样例:

Output

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

  将总括出的最少改换次数根据输入数据的次序输出。相应数据无解时输出-1。

Sample Output
2
-1

 

C语言达成代码如下:

 

#include "stdio.h"
#include "stdlib.h"
#define size 100
int num; //输入几组数据 
int row; //行数
int 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++;
}
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]) // 拷贝数组 
{
  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); //保护原始数组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;
   else exchgmin[i]=-1;
  }
  for(i=0;i<num;i++)
   printf("%d/n",exchgmin[i]);
  system("pause");
  return 0;
}

代码是外人的,认为写的很好。写这一个博客,主假诺想要重温一下思路。

愿意本文所述对我们C程序算法设计的上学抱有协理。

枚举1~m中,每一名列第叁列的动静,

您恐怕感兴趣的稿子:

//从1~n行,找寻不满意的行,实行一回行转变

//尽管所枚举的那1列能够成功依照规则转变来指标矩阵,则,此时的矩阵与原矩阵的距离只会在列序上

那时,从i=二 列(第一列)开头与指标矩阵的第i列实行相比较,

若不相同,搜索本矩阵中第j列(就=
i+1~m)是还是不是有与对象矩阵的第i列同样的,若有,且 本矩阵第j列!=
指标矩阵第j列,则,举办1次列转变

//即使找不到符合条件的列,则所枚举的这一名列第二列是不也许按所给规则转换成对象矩阵的

 

  1 #include<stdio.h>
  2 
  3 const int inf = 99999;
  4 const int N = 101;
  5 
  6 int a[N][N],b[N][N],temp[N][N]; //a存储初始矩阵,b为目标状态矩阵
  7 int n,m;
  8 int need;//需要变换次数
  9 
 10 void ChangeL(int x,int y)//变换列
 11 {
 12     if(x==y)return;
 13     int i;
 14     for(i=1;i<=n;i++)
 15     {
 16         int tt=temp[i][y];
 17         temp[i][y]=temp[i][x];
 18         temp[i][x]=tt;
 19     }
 20     need++;
 21 }
 22 
 23 void ChangeH(int x)//变换行
 24 {
 25     int i;
 26     for(i=1;i<=m;i++)
 27     {
 28         temp[x][i]^=1;
 29     }
 30 }
 31 
 32 
 33 bool Same(int x,int y) //判断列是否满足条件
 34 {
 35     int i;
 36     for(i=1;i<=n;i++)
 37         if(b[i][x]!=temp[i][y])return false;
 38     return true;
 39 }
 40 
 41 
 42 int main()
 43 {
 44     int tests;
 45     scanf("%d",&tests); //数据组数
 46     
 47     while(tests--)
 48     {
 49         scanf("%d%d",&n,&m); //n行,m列
 50         int i,j;
 51         for(i=1;i<=n;i++)
 52             for(j=1;j<=m;j++)
 53             {
 54                 scanf("%d",&a[i][j]);
 55             }
 56 
 57             for(i=1;i<=n;i++)
 58                 for(j=1;j<=m;j++)
 59                     scanf("%d",&b[i][j]);
 60 
 61             int k;
 62             int ans=inf; //ans存储最终答案,初始值为无穷大
 63 
 64 
 65             for(k=1;k<=m;k++)//枚举各列为第一列
 66             {
 67                 for(i=1;i<=n;i++)
 68                     for(j=1;j<=m;j++)
 69                         temp[i][j]=a[i][j];
 70                 need=0;
 71                 ChangeL(1,k);
 72 
 73 
 74                 //不满足的行,进行一次变换
 75                 for(i=1;i<=n;i++)
 76                 {
 77                     if(temp[i][1]!=b[i][1])//该行不满足条件
 78                     {
 79                         ChangeH(i);//变换行
 80                         need++;
 81                     }
 82                 }
 83 
 84 
 85                 bool find;
 86                 for(i=1;i<=m;i++)//检查每列是否满足条件
 87                 {
 88                     find=false;
 89                     if(Same(i,i))
 90                     {
 91                         find=true;
 92                         continue;
 93                     }
 94                     for(j=i+1;j<=m;j++)//寻找temp中与b的i列相同的列
 95                     {
 96                         if(Same(i,j))//temp 的 j列于b的i列相同
 97                         {
 98                             if(Same(j,j))continue;//temp的j列与b的j列相同
 99                             ChangeL(i,j);//交换temp的i,j列
100                             find=true;
101                             break;
102                         }
103                     }
104                     if(find==false)//找不到该列对应列
105                     {
106                         break;
107                     }
108                 }
109 
110 
111                 if(find==true&&need<ans)
112                     ans=need;
113             }
114 
115 
116             if(ans<inf)
117                 printf("%d\n",ans);
118             else
119                 printf("-1\n");
120     }
121     return 0;
122 }

参照他事他说加以考察资料:http://blog.csdn.net/sftxlin/article/details/7282645

 

留下评论

网站地图xml地图