Description

有$m× n(m≤100,n≤100)$个金币在桌面上排成一个$m$行$n$ 列的金币阵列。每一枚金币或正面朝上或背面朝上。用数字表示金币状态，$0$表示金币正面朝上，$1$ 表示背面朝上。金币阵列游戏的规则是：
（1）每次可将任一行金币翻过来放在原来的位置上；
（2）每次可任选$2$ 列，交换这$2$ 列金币的位置。
给定金币阵列的初始状态和目标状态，计算按金币游戏规则，将金币阵列从初始状态变换到目标状态所需的最少变换次数。

Input

输入数据有多组数据。第$1$行有$1$ 个正整数$k$，表示有$k$ 组数据。每组数据的第$1$ 行有$2$ 个正整数$m$ 和$n$。以下的$m$行是金币阵列的初始状态，每行有$n$ 个数字表示该行金币的状态，$0$ 表示金币正面朝上，$1$ 表示背面朝上。接着的$m$行是金币阵列的目标状态。

Output

将计算出的最少变换次数按照输入数据的次序输出。相应数据无解时输出 $-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

问题分析

思想和官方类似,设将初始状态的数组$a$的每一列$k$看作第一列,每种情况取最小值(若都不成立,则输出$-1$),反向求到初始状态数组$a$的情况,故

• 首先将最终状态数组$b$(记得备份最终状态数组$b$的原状态)第$k$列与第一列交换,初始化$cnt=0$;
• 然后看第$1$列中对应的行是否相同,不相同则让该行进行翻转且$cnt+=1$;
• 其次处理剩下的列去找是否存在对应的列与最初状态的数组$a$中的某一列相同,若存在,则交换且$cnt+=1$,否则不存在,继续将$k+1$列作为第$1$列处理;
• 最后如果所有的都找到与之对应的列进行交换,更新结果即可。

注意: 若正方向求,结果反而不对(分析不出来原因)

官方题解

代码实现

发现网上很多方法都过不了,贪心的思想不对,先处理行,再处理列,当时想着可能对,结果不对

• $WA$的代码

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/

#include<iostream>
#include<cstring>
#include<algorithm>

#define MAXN 110

using namespace std;

typedef long long ll;

int t;
int n,m;
int a[MAXN][MAXN],b[MAXN][MAXN];

int check1(int num)
{
    int cnt1=0,cnt0=0,sum=0;
    for(int i=1;i<=m;i++)
    {
        if(a[num][i]==0)
            cnt0++;
        if(b[num][i]==1)
            cnt1++;
        if(a[num][i]==b[num][i])
            sum++;
    }
    if(sum==m)
        return 2;
    else if(cnt1==cnt0)
        return 1;
    else return 0;
}

void change1(int num)
{
    for(int i=1;i<=m;i++)
        a[num][i]^=1;
}

int check2(int num)
{
    int pos=0;
    for(int i=1;i<=m;i++)
    {
        if(i==num)
            continue;
        int sum=0;
        for(int j=1;j<=n;j++)
            if(b[j][num]==a[j][i])
                sum++;
        if(sum==n)
        {
            pos=i;
            break;
        }
    }
    return pos;
}

void change2(int num1,int num2)
{
    for(int i=1;i<=n;i++)
    {
        int t=a[i][num1];
        a[i][num1]=a[i][num2];
        a[i][num2]=t;
    }
}

int check()
{
    int sum=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(a[i][j]==b[i][j])
                sum++;
    return sum==n*m;
}

int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    cin >> t;
    while(t--)
    {
        int res=0;
        cin >> n >> m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin >> a[i][j];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin >> b[i][j];
        for(int i=1;i<=n;i++)//a中当前行中1(或0)的个数与b中0(或1)的个数相同,翻转
            if(check1(i)==1)
            {
                change1(i);
                res++;
            }
        for(int i=1;i<=m;i++)
        {
            int j=check2(i);
            if(j>i)
            {
                change2(i,j);
                res++;
            }
        }
        if(check())
            cout << res << endl;
        else cout << -1 << endl;
    }
    return 0;
}

• $AC$的代码

/**
  * @author  : SDTBU_LY
  * @version : V1.0.0
  * @上联    : ac自动机fail树上dfs序建可持久化线段树
  * @下联    : 后缀自动机的next指针DAG图上求SG函数
**/

#include<iostream>
#include<cstring>
#include<algorithm>
#include<vector>

#define MAXN 110

using namespace std;

typedef long long ll;

const ll inf=0x3f3f3f3f3f3f3f3f;
int t,n,m;
ll cnt;
int a[MAXN][MAXN],b[MAXN][MAXN],temp[MAXN][MAXN];

int check(int num1,int num2)
{
    for(int i=1;i<=n;i++)
        if(a[i][num1]!=b[i][num2])
            return 0;
    return 1;
}


void change1(int num)
{
    for(int i=1;i<=m;i++)
        b[num][i]^=1;
}

void change2(int num1,int num2)
{
    if(num1==num2)
        return ;
    else if(num1!=num2)
    {
        cnt++;
        for(int i=1;i<=n;i++)
        {
            int t=b[i][num1];
            b[i][num1]=b[i][num2];
            b[i][num2]=t;
        }
    }
}


int main()
{
    // ios::sync_with_stdio(false);
    // cin.tie(0),cout.tie(0);
    cin >> t;
    while(t--)
    {
        ll res=inf;
        cin >> n >> m;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin >> a[i][j];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                cin >> b[i][j];
        memcpy(temp,b,sizeof(temp));
        for(int k=1;k<=m;k++)
        {
            cnt=0;
            memcpy(b,temp,sizeof(temp));
            change2(1,k);
            for(int i=1;i<=n;i++)
                if(a[i][1]!=b[i][1])
                {
                    change1(i);
                    cnt++;
                }

            int found=0;

            for(int i=1;i<=m;i++)
            {
                found=0;
                for(int j=i;j<=m;j++)
                {
                    if(check(i,j))
                    {
                        change2(i,j);
                        found=1;
                        break;
                    }
                }
                if(found==0)
                    break;
            }
            if(found==1&&cnt<res)
                res=cnt;
        }
        if(res<inf)
            cout << res << endl;
        else  cout << -1 << endl;
    }
    return 0;
}