鸭蛋求助QAQ
  • 板块P1275 魔板
  • 楼主cougarmace
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/3/12 07:53
  • 上次更新2023/10/23 21:49:50
查看原帖
鸭蛋求助QAQ
339335
cougarmace楼主2023/3/12 07:53
#include<iostream>
#include<queue>
#include<map>
#include<set>
using namespace std;;
int q,n,m,a[10010][10010],b[10010][10010],sum1,sum2;
string change_w(string s,int x){//行变换
    for(int i=0;i<m;i++){
        if(s[x*m+i]=='1')s[x*m+i]='0';
        else s[x*m+i]='1';
    }
    return s;
}
string change_h(string s,int x,int y){//列变换
    for(int i=0;i<n;i++){
        swap(s[i*m+x],s[i*m+y]);
    }
    return s;
}
int main(){
    cin>>q;
    while(q--){
        queue<string> q;
        cin>>n>>m;string s1,s2;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>a[i][j];
                if(a[i][j]==1)sum1++;
                s1+=char(a[i][j]+'0');//转换为字符串方便map查重
            }
        }for(int i=1;i<=n;i++){
            for(int j=1;j<=m;j++){
                cin>>b[i][j];
                if(b[i][j]==1)sum2++;
                s2+=char(b[i][j]+'0');
            }
        }
        if(sum1!=sum2){
            cout<<"NO"<<endl;
            break;
        }
        // cout<<s1<<endl;
        // string ppp=change_h(s1,1,2);
        // for(int i=0;i<ppp.length();i++){
        //     cout<<ppp[i];
        //     if((i+1)%m==0)cout<<endl;
        // }
        map<string,bool> vis;
        int p=0;
        vis[s1]=1;
        q.push(s1);
        while(!q.empty()){
            string f=q.front();
            q.pop();
            vis[f]=1;
            if(f==s2){
                p=1;
                cout<<"YES"<<endl;;
                break;
            }
            for(int i=0;i<n;i++){
                string k=change_w(f,i);
                if(!vis[k]){
                    q.push(k);
                }
            }
            for(int i=0;i<m;i++){
                for(int j=i+1;j<m;j++){
                    string k=change_h(f,i,j);
                    if(!vis[k]){
                        q.push(k);
                    }
                }
            }
        }
        if(p==0){
            cout<<"NO"<<endl;
        }
    }
    return 0;
}
2023/3/12 07:53
加载中...