记录编号	270489	评测结果	AAAAA
题目名称	魔板游戏	最终得分	100
用户昵称	Riolu	是否通过	通过
代码语言	C++	运行时间	0.017 s
提交时间	2016-06-14 21:04:04	内存使用	1.70 MiB

/*=========================================*
  * Auther: Riolu
  * PID:
  * Time: 2016.
  * ?Copyright 2016 Riolu. All Rights Reserved.
  *=========================================*/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<ctime>
#define N 101
using namespace std;
/*=========DEFINE============================*/
int n,m,ans;
bool e[N][N],s[N][N];           //e[][]表示初始状态 s[][]表示终止状态
int h[2][N];                    //h[0][]表示初始状态每一行亮灯数, h[1][]表示终止状态每一行亮灯数
int bo[N][N][N];                //bo[x][i][j]==1表示在前x行的搜索结果下,第i列不能与终止状态的第j列匹配
/*=========JUDGE==============================*/
int ju2(){                      //判断终止状态每一列是否都有初始状态的一列与之对应
    int i,j,x,k;
    k=1;
    for(i=1;i<=m;i++){
        if(k==0)break;k=0;
        for(j=1;j<=m;j++)if(!bo[n][j][i]){k=1;break;}
        }
    return k;
}
/*=========DFS==============================*/
void dfs(int x){
    int i,j,k;
    if(ans==1)return;           //已搜到答案迅速返回
    if(x==n+1){                 //搜到第n+1行进行判断
    if(ju2()){ans=1;cout<<"YES"<<endl;}return;}
    if(h[0][x]==h[1][x]){                                               //在此行不改变所有灯泡的状态,亮灯数匹配
        for(i=1;i<=m;i++)for(j=1;j<=m;j++)bo[x][i][j]=bo[x-1][i][j];    //把上一行的的状态更新到本行
        for(i=1;i<=m;i++){
            if(e[x][i]){for(j=1;j<=m;j++){if(!s[x][j])bo[x][i][j]=1;}}  //第i列不能与终止状态的第j列匹配
            if(!e[x][i]){for(j=1;j<=m;j++){if(s[x][j])bo[x][i][j]=1;}}
        }
        k=1;
        for(i=1;i<=m;i++){      //此列无对应终止状态匹配时剪枝
            if(k==0)break;k=0;
            for(j=1;j<=m;j++)if(!bo[x][i][j]){k=1;break;}
            }
        if(k==1)dfs(x+1);       //存在匹配,搜下一行
    }
    if(h[0][x]+h[1][x]==m){                                             //在此行不改变所有灯泡的状态,亮灯数匹配
        for(i=1;i<=m;i++)for(j=1;j<=m;j++)bo[x][i][j]=bo[x-1][i][j];    //接下来与上面相同
        for(i=1;i<=m;i++)e[x][i]=!e[x][i];
        for(i=1;i<=m;i++){
            if(e[x][i]){for(j=1;j<=m;j++){if(!s[x][j])bo[x][i][j]=1;}}
            if(!e[x][i]){for(j=1;j<=m;j++){if(s[x][j])bo[x][i][j]=1;}}
        }
        k=1;
        for(i=1;i<=m;i++){
            if(k==0)break;k=0;
            for(j=1;j<=m;j++)if(!bo[x][i][j]){k=1;break;}
            }
        if(k==1)dfs(x+1);
        }
}
/*=========READ==============================*/
void read(){
	freopen("panel.in","r",stdin);
	freopen("panel.out","w",stdout);
	int i,j,x,y,k,nn;
	ios::sync_with_stdio(false);
    cin>>nn;
    for(i=1;i<=nn;i++){
        memset(bo,0,sizeof(bo));
        memset(h,0,sizeof(h));
        cin>>n>>m;
        for(k=1;k<=n;k++)for(j=1;j<=m;j++){cin>>e[k][j];if(e[k][j])h[0][k]++;}
        for(k=1;k<=n;k++)for(j=1;j<=m;j++){cin>>s[k][j];if(s[k][j])h[1][k]++;}
        ans=0;dfs(1);
        if(ans==0)cout<<"NO"<<endl;
        }
	}
/*=========MAIN==============================*/
int work()
{
	read();
	return 0;
}
int Riolu=work();
int main(){;}