C语言金币阵列问题解决方法
本文实例详细讲述了C语言实现金币阵列问题的解决方法,分享给大家供大家参考。具体方法如下:
问题描述:
有m*n(1 ≤ m, n ≤ 100)个金币在桌面上排成一个 m 行 n 列的阵列。每一枚金币或正面朝上或背面朝上。用数字表示金币状态,0表示金币正面朝上,1 表示背面朝上。
金币阵列游戏的规则是:
1. 每次可将任一行金币翻过来放在原来的位置上;
2. 每次可任选 2 列,交换这 2 列金币的位置。
本题要求对于给定的金币阵列初始状态和目标状态,编程计算按金币游戏规则,将金币阵列从初始状态变换到目标状态所需的最少变换次数。
数据输入:
输入的测试数据的第一行是一个不超过 10 的正整数 k,表示有 k 个测试用例. 每个测试用例的第一行是两个正整数 m, n. 接下来是 m 行,每行有 n 个用空白符分隔的 0 或 1. 这 m*n 个 0-1 表示金币的初始状态阵列。最后是 m 行,每行 n 个 用空白符分隔的 0 或 1,表示金币阵列的目标状态。
数据输出:
对于每个测试用例,输出一行包含一个整数,表示按照要求规则将金币阵列从初始状态变换为目标状态所需要的最少变换次数。如果不能按照变换规则将初始状态变换为目标状态(即无解时)则输出 -1。
数据样例:
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语言实现代码如下:
#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程序算法设计的学习有所帮助。
相关文章
- 这篇文章主要为大家详细介绍了C语言实现放烟花的程序,有音乐播放,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下...2021-02-23
- 本篇文章主要介绍C语言中char的知识,并附有代码实例,以便大家在学习的时候更好的理解,有需要的可以看一下...2020-04-25
- 这篇文章主要介绍了详解如何将c语言文件打包成exe可执行程序,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-25
- free函数是释放之前某一次malloc函数申请的空间,而且只是释放空间,并不改变指针的值。下面我们就来详细探讨下...2020-04-25
- 这篇文章主要介绍了C语言中计算正弦的相关函数总结,包括正弦和双曲线正弦以及反正弦的函数,需要的朋友可以参考下...2020-04-25
详解C语言中的rename()函数和remove()函数的使用方法
这篇文章主要介绍了详解C语言中的rename()函数和remove()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25- 这篇文章主要介绍了C语言中求和、计算平均值、方差和标准差的实例,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-12-10
- 本篇文章主要讲解C语言 基本语法,这里提供简单的示例和代码来详细讲解C语言的基本语法,开始学习C语言的朋友可以看一下,希望能够给你带来帮助...2021-09-18
- 这篇文章主要介绍了C语言中send()函数和sendto()函数的使用方法,是C语言入门学习中的基础知识,需要的朋友可以参考下...2020-04-25
- 今天小编就为大家分享一篇C语言实现从文件读入一个3*3数组,并计算每行的平均值,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言中memcpy 函数的用法详解的相关资料,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了使用C语言操作文件的基本函数整理,包括创建和打开以及关闭文件的操作方法,需要的朋友可以参考下...2020-04-25
- 这篇文章主要介绍了C语言中查找字符在字符串中出现的位置的方法,分别是strchr()函数和strrchr()函数的使用,需要的朋友可以参考下...2020-04-25
- 很多同学在学习c语言的时候是不是会碰到a++和++a都有甚么作用啊。今天我们就来探讨下...2020-04-25
- 这篇文章主要对C语言中const关键字的用法进行了详细的分析介绍,需要的朋友可以参考下...2020-04-25
- 下面小编就为大家带来一篇C语言实现时间戳转日期的算法(推荐)。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧...2020-04-25
- 这篇文章主要介绍了C语言之整数划分问题(递归法)实例代码的相关资料,需要的朋友可以参考下...2020-04-25
- 本文给大家简单介绍下c实现linux下的数据库备份的方法和具体的源码,十分的实用,有需要的小伙伴可以参考下。...2020-04-25
C语言正则表达式详解 regcomp() regexec() regfree()用法详解
C语言处理正则表达式常用的函数有regcomp()、regexec()、regfree()和regerror(),这里就为大家介绍一下,需要的朋友可以参考一下啊...2020-04-25- 这篇文章主要介绍了c语言实现找最大值最小值位置查找,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧...2021-02-04