51nod 1851 俄罗斯方块

玩过俄罗斯方块？那你知道俄罗斯方块共有七种吧（其实只有五种）

给一个黑白图，每次能将某些区域的格子黑白反转，至于某些区域的意思嘛，就是俄罗斯方块形状的区域咯（可水平翻转、上下翻转、旋转）

求能否将图变成全白

Input

多组数据，第一行一个正整数 T，表示数据组数

每组数据中第一行两个正整数 n,m，表示图的长和宽

接下来 n 行，每行 m 个数字，表示第 i 行第 j 列的格子的颜色，0为白，1为黑

T<=1000，∑n*m<=10000000

Output

对于每组数据，若能将图变成全白，则输出一行字符串"Yes"，否则输出"No"（不包含双引号）

Input示例

Output示例

Yes
————————————————————————————————————————————————————————————————————————————————
这道题呢 我们可以靠一个 2x2 的矩阵将所有的 1 都转换到最后一行 和 最后一列 
然后靠 1x4 将所有的一转换到最后一列 和 最下面一列 的三各
最后用 7 形状的  把问题转换成 右下角的三个格 
最后发现偶数有解 奇数无解 
在这个过程中我们又发现最后的奇偶 和 原来矩阵的 奇偶一样 这个就自己证明把
当然 1x？ 和 2x2 需要特判一波

#include<stdio.h>

#include<cstring>

#include<algorithm>

using namespace std;

const int M=;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int ans,T,n,m;

bool s[M];

char c;

bool isdigit(char c) {return c>='' && c<='';}

int main()

{

    T=read();

    while(T--){

        n=read(); m=read();

        if(n>m) swap(n,m);

        while (!isdigit(c=getchar()));

        if (n==){

            for (int i=;i<m;i++) {s[i]=(c-''); while(!isdigit(c=getchar()));}

            s[m]=(c-'');

            for (int i=;i<=m-;i++)

                if(s[i]) for(int j=;j<=;j++) s[i+j]^=;

            if (s[m-]||s[m-]||s[m]) printf("No\n");

            else printf("Yes\n");

        }

        else if (n==&&m==){

            int ans=;

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

                ans+=(c-'');

                while (!isdigit(c=getchar()));

            }

            ans+=(c-'');

            if(ans==||!ans) printf("Yes\n");

            else printf("No\n");

        }

        else{

            int ans=;

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

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

                {

                    if (i==n&&j==m) break;

                    ans+=(c-'');

                    while (!isdigit(c=getchar()));

                }

            ans+=(c-'');

            if (ans%) printf("No\n");

            else printf("Yes\n");

        }

    }

    return ;

}

巴特西

51nod 1851 俄罗斯方块

最新文章

热门文章