自动搬运

查看原文

来自洛谷，原作者为

	Ellen7ions **

搬运于2025-08-24 21:23:13，当前版本为作者最后更新于2018-10-31 19:53:36，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

大佬们的题解真是简洁，然而我这种蒟蒻并没有看懂，然后自己手玩一下好像挺简单？

-----------------------------------------华丽分割线--------------------------------------

你在手玩的时候可以看见几个性质：

①：每一行最多翻转一次，多于一次其实没有意义。

②：每一列的交换只不过改变了每一列的元素的位置。假设这个魔板只又一种操作，即令某几列交换，那么我们总可以找到一种排列顺序，使得它和目标魔板相同。

所以，我们可以只关心原魔板某一列和目标魔板的任意一列匹配就可以了，我们通过转换操作，使得这一列和目标魔板的随便一列（大家好像都选的第一列），匹配的同时，让其他列也跟着转换，最后判断一下目标魔板，除了第一列以外的所有，是否和当前魔板一样就可以了。

具体见代码。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#define mem(a, i) memset(a, i, sizeof(a))
#define rep(i, a, b) for(int i = a; i <= b ; i++)
const int maxn = 128;
using namespace std;
int n, m, k, f;
int map[maxn][maxn], tar[maxn][maxn], temp[maxn][maxn];
//转换 i 行操作。 
void converse(int i) { rep(j, 1, m)	map[i][j] = !map[i][j]; }
// 判断目标魔板除了第一列以外时候都和当前魔板匹配。 
bool Check(int choose) {
	bool vis[maxn];
	mem(vis, 0);
	rep(jt, 2, m) {
		rep(jp, 1, m) {
			if(jp == choose)	continue;
			bool pd = 0;
			rep(i, 1, n)
				if(map[i][jp] != tar[i][jt]) {
					pd = 1;
					break;
				}
			if(!pd && !vis[jt])	{
				vis[jt] = 1;
				break;
			}		
		}
	}
	rep(i, 2, m)	if(!vis[i])	return false;
	return true;
}
//将原魔板的 cur 列， 强制和目标魔板的第 1 列 匹配。
//伴随着，也把原魔板的其他列也翻转。 
void Search(int cur) {
	rep(i, 1, n)
		if(map[i][cur] != tar[i][1]) //不同就翻转 
			converse(i);
	return ;
}
//复原 
void Getback() {
	rep(i, 1, n)
		rep(j, 1, m)
			map[i][j] = temp[i][j];
	return ;
}
int main() {
	scanf("%d", &k);
	rep(p, 1 ,k) {
		mem(map, 0);
		mem(tar, 0);
		mem(temp, 0);
		f = 0;
		scanf("%d %d", &n, &m);
		//读入原魔板 
		rep(i, 1, n)
			rep(j, 1, m)
				scanf("%d", &map[i][j]),
				temp[i][j] = map[i][j];
		//读入目标魔板 
		rep(i, 1, n)
			rep(j, 1, m)
				scanf("%d", &tar[i][j]);
		//枚举原魔板的 i 列，使其和目标魔板匹配。 
		rep(i, 1, m) {
			Search(i); 
			if(Check(i)) {
				f = 1;
				printf("YES\n");
				break;
			}
			Getback();	//记得复原 
		}
		if(!f)	printf("NO\n");
	}
	return 0;
}