金币阵列问题-白红宇

金币阵列问题

阅读量：4343 次

发布时间：2019-06-07

本文共 2160 字，大约阅读时间需要 7 分钟。

问题描述：

有mxn(m <= 100,n <= 100)个金币在桌面上排成一个m行n 列的金币阵列。每一枚金

币或正面朝上或背面朝上。用数字表示金币状态，0表示金币正面朝上，1 表示背面朝上。

金币阵列游戏的规则是：

（1）每次可将任一行金币翻过来放在原来的位置上；

（2）每次可任选2 列，交换这2 列金币的位置。

算法设计：

给定金币阵列的初始状态和目标状态，计算按金币游戏规则，将金币阵列从初始状态变

换到目标状态所需的最少变换次数。

数据输入：

文件中有多组数据。文件的第1行有1 个正整数k，表示有k 组数据。每组数据的第1 行有2 个正整数m 和n。

以下的m行是金币阵列的初始状态，每行有n 个数字表示该行金币的状态，0 表示金币正面朝上，1 表示背面朝上。

接着的m行是金币阵列的目标状态。

«结果输出:

相应数据无解时输出-1。

输入文件示例

4 3

1 0 1

0 0 0

1 1 0

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

1.思路是从1-n，逐列枚举其为第1列。然后再对不满足的行进行变化

最后的差别会只在列上面。

代码采用了hash，所以复杂度位O（mn^2),复杂到没有明显的bug ^_^

下面这个链接：最直接的写法，简单到明显没有bug

“There are two ways of constructing a software design. One way is to make it so simple that there are obviously no deficiencies. And the other way is to make it so complicated that there are no obvious deficiencies.”- C.A.R. Hoare

　　设计软件有两种方法：一种是简单到明显没有缺陷，另一种复杂到缺陷不那么明显。—— 托尼·霍尔

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              using namespace std;const int maxn=108;char a[maxn][maxn],b[maxn][maxn],temp[maxn][maxn];int s1[maxn],s2[maxn];const int N=136;const int mod = 131;unsigned int ELFhash(char* url){ unsigned int h = 0, g; while (*url) { h = (h << 4) + *url++; g = h & 0xF0000000; if (g) h ^= g >> 24; h &= ~g; } return h % mod;}char mp[N][maxn];int head[N], nxt[N], e = 1;//e=0;int msn[N];inline int Find_hash(int u,char* x){ for (int i = head[u]; i ; i = nxt[i]) if (!strcmp(mp[i], x)) return i; return 0;}inline int Insert_hash(int u,char* x){ strcpy(mp[e], x); nxt[e] = head[u]; head[u] = e++; return head[u];}//hash 仅调用一次，可不初始化void init_hash(){ //i!=-1 e = 1;//e=0; memset(head, 0, sizeof(head[0])*mod); //mem(,-1,)}int m,n,nCount;int Rchar(){ int c; while (!isdigit(c = getchar())); return c;}int init();void solve();int main(){ int t;scanf("%d",&t); while(t--) { if(init() != -1) solve(); else puts("-1"); } return 0;}void input(char a[maxn][maxn],int s1[]){ memset(s1,0,sizeof(s1[0])*m); for(int i=0;i