P3585 [POI2015]PIE

题目描述

一张n*m的方格纸，有些格子需要印成黑色，剩下的格子需要保留白色。你有一个a*b的印章，有些格子是凸起（会沾上墨水）的。你需要判断能否用这个印章印出纸上的图案。印的过程中需要满足以下要求：（1）印章不可以旋转。（2）不能把墨水印到纸外面。（3）纸上的同一个格子不可以印多次。

输入输出格式

输入格式：

第一行一个整数q(1<=q<=10)，表示测试点数量。接下来q个测试点，每个测试点中：第一行包含4个整数n,m,a,b(1<=n,m,a,b<=1000)。接下来n行，每行m个字符，描述纸上的图案。'.'表示留白，'x'表示需要染黑。接下来a行，每行b个字符，描述印章。'.'表示不沾墨水，'x'表示沾墨水。

输出格式：

对于每个测试点，输出TAK（是）或NIE（否）。

输入输出样例

输入样例#1：

2

3 4 4 2

xx..

.xx.

xx..

x.

.x

x.

..

2 2 2 2

xx

xx

.x

x.

输出样例#1：

TAK

NIE

说明

一张n*m的方格纸，有些格子需要印成黑色，剩下的格子需要保留白色。

你有一个a*b的印章，有些格子是凸起（会沾上墨水）的。你需要判断能否用这个印章印出纸上的图案。印的过程中需要满足以下要求：

（1）印章不可以旋转。

（2）不能把墨水印到纸外面。

（3）纸上的同一个格子不可以印多次。

思路：模拟。

#include<cstdio>

#include<iostream>

#include<cstring>

using namespace std;

int tx,ty,num,n,m,a,b,cou,top;

int map[][],gzx[],gzy[],yzx[],yzy[];

char ch[];

bool flag;

bool judge(int x,int y) {

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

        tx=x+yzx[i];ty=y+yzy[i];

        if(tx>n||ty>m||!tx||!ty)    return ;

        if(!map[tx][ty])    return ;

        else     map[tx][ty]=;

    }

    return ;

}

int main(){

    scanf("%d",&num);

    while(num--){

        memset(map,,sizeof(map));

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

        top=cou=;

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

            scanf("%s",ch+);

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

                if(ch[j]=='x'){

                    top++;

                    gzx[top]=i;

                    gzy[top]=j;

                    map[i][j]=top;

                }

        }

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

            scanf("%s",ch+);

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

                if(ch[j]=='x'){

                    if(!cou)    tx=i,ty=j;

                    cou++;

                    yzx[cou]=i-tx;

                    yzy[cou]=j-ty;

                }

        }

        flag=;

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

            if(map[gzx[i]][gzy[i]])

                if(!judge(gzx[i],gzy[i])){

                    puts("NIE");

                    flag=;break;

                }

        if(!flag)

        puts("TAK");

    }

    return ;

}

巴特西

洛谷 P3585 [POI2015]PIE

P3585 [POI2015]PIE

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章