P1275 魔板

题目描述

有这样一种魔板：它是一个长方形的面板，被划分成n行m列的n*m个方格。每个方格内有一个小灯泡，灯泡的状态有两种(亮或暗)。我们可以通过若干操作使魔板从一个状态改变为另一个状态。操作的方式有两种：

（1）任选一行，改变该行中所有灯泡的状态，即亮的变暗、暗的变亮；

（2）任选两列，交换其位置。

当然并不是任意的两种状态都可以通过若干操作来实现互相转化的。

你的任务就是根据给定两个魔板状态，判断两个状态能否互相转化。

输入输出格式

输入格式：

文件中包含多组数据。第一行一个整数k，表示有k组数据。

每组数据的第一行两个整数n和m。(0<n，m≤100)

以下的n行描述第一个魔板。每行有m个数字(0或1)，中间用空格分隔。若第x行的第y个数字为0，则表示魔板的第x行y列的灯泡为“亮”；否则为“暗”。

然后的n行描述第二个魔板。数据格式同上。

任意两组数据间没有空行。

输出格式：

共k行，依次描述每一组数据的结果。

若两个魔板可以相互转化，则输出YES，否则输出NO。(注意：请使用大写字母)

输入输出样例

输入样例#1：

输出样例#1：

YES

NO

#include<iostream>

#include<cstdio>

#include<cstring>

#include<map>

#include<queue>

#define maxn 110

#define mod 10000003

using namespace std;

map<string,bool>vis;

int n,m,T,a[];

string t;

string s,cur,nxt;

queue<string>q;

string hash(int x[]){

    string res="";

    for(int i=;i<=n*m;i++)res+=x[i]+'';

    return res;

}

bool bfs(){

    while(!q.empty()){

        cur=q.front();q.pop();

        for(int i=;i<=n;i++){//枚举修改每一行

            int w=(i-)*m;

            nxt=cur;

            for(int j=;j<m;j++){

                if(nxt[w+j]=='')nxt[w+j]='';

                else nxt[w+j]='';

            }

            if(nxt==t)return ;

            if(!vis[nxt]){

                q.push(nxt);

                vis[nxt]=;

            }

        }

        for(int i=;i<m;i++){//枚举修改每一列

            nxt=cur;

            for(int j=;j<m;j++){

                if(nxt[i+j*m]=='')nxt[i+j*m]='';

                else nxt[i+j*m]='';

            }

            if(nxt==t)return ;

            if(!vis[nxt]){

                q.push(nxt);

                vis[nxt]=;

            }

        }

    }

    return ;

}

int main(){

    scanf("%d",&T);

    while(T--){

        while(!q.empty())q.pop();

        s="";t="";

        //memset(vis,0,sizeof(vis));

        vis.clear();

        scanf("%d%d",&n,&m);

        for(int i=;i<n*m;i++){

            scanf("%d",&a[i]);

            s+=a[i]+'';

        }

        for(int i=;i<n*m;i++){

            scanf("%d",&a[i]);

            t+=a[i]+'';

        }

        vis[s]=;

        q.push(s);

        if(bfs())printf("YES\n");

        else printf("NO\n");

    }

}

0分手模不出样例，我自己写的宽搜也没过

/*

    第一步:在最外层循环枚举初始的每一列当做目标状态的第一列

    第二步:在每层循环中比较当前这列和目标状态的第一列的同行的数，如果不相同则把初始的那一行翻转（前面先记录，后面记得还原）

    第三步:看看剩下的列是否可以一一对应，如果可以就yes，不可以就继续枚举。

*/

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

#define maxn 110

int n,m,T,s[maxn][maxn],t[maxn][maxn];

bool change_x[maxn],vis_y[maxn];

bool check(int x){

    memset(change_x,,sizeof(change_x));

    memset(vis_y,,sizeof(vis_y));

    for(int i=;i<=n;i++)

        if(s[i][x]!=t[i][])

            change_x[i]=;//第i行需要翻转

    vis_y[x]=;

    for(int i=;i<=m;i++){//目标状态的第i列

        bool flag=;

        for(int j=;j<=m;j++){//初始状态的第j列

            if(vis_y[j])continue;

            int cnt=;

            for(int k=;k<=n;k++){

                if((change_x[k]&&s[k][j]!=t[k][i])||(!change_x[k]&&s[k][j]==t[k][i]))cnt++;

                else break;

            }

            if(cnt==n){

                vis_y[j]=,flag=;

                break;

            }

        }

        if(!flag)return ;

    }

    return ;

}

int main(){

    freopen("Cola.txt","r",stdin);

    scanf("%d",&T);

    while(T--){

        scanf("%d%d",&n,&m);

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++)

                scanf("%d",&s[i][j]);

        for(int i=;i<=n;i++)

            for(int j=;j<=m;j++)

                scanf("%d",&t[i][j]);

        bool flag=;

        for(int i=;i<=m;i++){//枚举初始状态的每一列与目标状态对应

            int now=check(i);

            if(now==){

                printf("YES\n");

                flag=;break;

            }

        }

        if(!flag)printf("NO\n");

    }

}

100分

巴特西

洛谷P1275 魔板

P1275 魔板

题目描述

输入输出格式

输入输出样例

最新文章

热门文章