BZOJ 3750: [POI2015]Pieczęć 【模拟】

Description

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

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

（1）印章不可以旋转。

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

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

Input

第一行一个整数q(1<=q<=10)，表示测试点数量。

接下来q个测试点，每个测试点中：

第一行包含4个整数n,m,a,b(1<=n,m,a,b<=1000)。

接下来n行，每行m个字符，描述纸上的图案。'.'表示留白，'x'表示需要染黑。

接下来a行，每行b个字符，描述印章。'.'表示不沾墨水，'x'表示沾墨水。

Output

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

Sample Input

2
3 4 4 2
xx..
.xx.
xx..
x.
.x
x.
..
2 2 2 2
xx
xx
.x
x.

Sample Output

TAK
NIE

HINT

Source

鸣谢Jcvb

思路：由于左上的点肯定是对应的因此每次寻找左上的点把印章里的点覆盖掉模拟一边即可

#include<cstdio>

#include<string.h>

#include<algorithm>

#define maxn 1009

using namespace std;

struct T

{int x;int y;}z[maxn*maxn];

int h,a,b,c,d,ma[maxn][maxn],t;

char ch[maxn];

int main(){

scanf("%d",&t);

while(t--){

scanf("%d%d%d%d",&a,&b,&c,&d);

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

scanf("%s",ch+1);

for(int j=1;j<=b;j++)if(ch[j]=='.')ma[i][j]=1;else ma[i][j]=2;

}

int flag=h=0;

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

scanf("%s",ch+1);

for(int j=1;j<=d;j++)

if(ch[j]=='x'&& flag==0)flag=1,z[++h].x=i,z[h].y=j;

else if(ch[j]=='x')z[++h].x=i-z[1].x,z[h].y=j-z[1].y;

}flag=0;

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

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

if(ma[i][j]==2){ma[i][j]=1;

for(int k=2;k<=h;k++){

if(x>=1&&y>=1&&ma[i+z[k].x][j+z[k].y]==2)ma[i+z[k].x][j+z[k].y]=1;

else{flag=1;break;}

}if(flag==1)break;

}

}if(flag==1)break;

}

if(flag==0)printf("TAK\n");else printf("NIE\n");

for(int i=1;i<=a;i++)for(int j=1;j<=b;j++)ma[i][j]=0;

}

return 0;

}

巴特西

BZOJ 3750: [POI2015]Pieczęć 【模拟】

最新文章

热门文章