题解 P1275 【魔板】

· · 题解

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

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

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

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

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

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

具体见代码。

#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;
}