金币阵列问题

问题描述：

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

金币阵列游戏的规则是：

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

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

任务：给定金币的初始状态和目标状态，编程计算按金币游戏规则，将金币排列从初始状态变换到目标状态所需的最少变换次数。

解题思路：

本例的实质是将一个二进制矩阵从一种形式利用相应规则变换到另一种形式。提供的规则有两种：

(1）将某一行的金币翻转；
(2）将某两列进行交换。

在这两种操作中，第一种操作可能会影响到某一行或者某一列中已经排列好的相关元素，因此，首先利用该规则进行变换，而后续的操作则不再利用该规则。算法的具体思路如下：

(1）将矩阵中的每一列作为第1列，并利用第一个规则将第1列中的相关元素与目标矩阵中第1列的元素进行配对，如果不相同，则利用每1个规则进行翻转；

(2）从第2列开始，将处理后的列与目标列进行比较，如果相同，则转下一列；如果不相同，看是否可以通过列的交换完成，如果不可以，则无法做到，如果可以，则继续扫描，直至所有的列描述完成为止。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;
typedef long long LL;
const int maxn = 15;
int m, n;
int src[maxn][maxn], des[maxn][maxn];
int cnt, tmp[maxn][maxn];

void copy(int a[maxn][maxn], int b[maxn][maxn]){
	for(int i = 1; i <= m; ++i)
		for(int j = 1; j <= n; ++j)
			a[i][j] = b[i][j];
}

void trans1(int r){
	for(int j = 1; j <= n; ++j) tmp[r][j] = tmp[r][j]^1;
	++cnt;
}

void trans2(int c1, int c2){
	for(int i = 1; i <= m; ++i) swap(tmp[i][c1], tmp[i][c2]);
	if(c1 != c2) ++cnt;
}

bool same(int c1, int c2){
	for(int i = 1; i <= m; ++i) if(des[i][c1] != tmp[i][c2]) return false;
	return true;
}


int main()
{
	//freopen("in.txt","r",stdin);
	int T; scanf("%d",&T);
	while(T--){
		scanf("%d%d",&m,&n);
		for(int i = 1; i <= m; ++i)
			for(int j = 1; j <= n; ++j)
				scanf("%d",&src[i][j]);
		for(int i = 1; i <= m; ++i)
			for(int j = 1; j <= n; ++j)
				scanf("%d",&des[i][j]);
				
		int best = m + n + 1;
		for(int col = 1; col <= n; ++col){//在tmp中依次寻找des的每一列
			copy(tmp, src);
			cnt = 0; trans2(1, col);
			for(int i = 1; i <= m; ++i) if(tmp[i][1] != des[i][1]) trans1(i);
			bool found;
			for(int c1 = 1; c1 <= n; ++c1){
				found = false;
				for(int c2 = c1; c2 <= n; ++c2)
					if(same(c1, c2)){ trans2(c1, c2); found = true; break; }
				if(!found) break;
			}
			if(found&&best > cnt) best = cnt;
		}
		
		if(best < m+n+1 ) printf("%d\n", best);
		else printf("-1\n");
	}
	fclose(stdin);
	return 0;
}

/*
输入:
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
输出：
2
-1
*/