源码网商城,靠谱的源码在线交易网站 我的订单 购物车 帮助

源码网商城

c语言:金币阵列的问题

  • 时间:2020-05-03 12:23 编辑: 来源: 阅读:
  • 扫一扫,手机访问
摘要: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列,则,进行一次列变换 //若是找不到符合条件的列,则所枚举的这一列为第一列是不可能按所给规则变换到目标矩阵的
[u]复制代码[/u] 代码如下:
#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;  }
  • 全部评论(0)
联系客服
客服电话:
400-000-3129
微信版

扫一扫进微信版
返回顶部