题目描述
一张n*m的方格纸，有些格子需要印成黑色，剩下的格子需要保留白色。
你有一个a*b的印章，有些格子是凸起（会沾上墨水）的。你需要判断能否用这个印章印出纸上的图案。印的过程中需要满足以下要求：
（1）印章不可以旋转。
（2）不能把墨水印到纸外面。
（3）纸上的同一个格子不可以印多次。
你有一个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'表示沾墨水。
接下来q个测试点，每个测试点中：
第一行包含4个整数n,m,a,b(1<=n,m,a,b<=1000)。
接下来n行，每行m个字符，描述纸上的图案。'.'表示留白，'x'表示需要染黑。
接下来a行，每行b个字符，描述印章。'.'表示不沾墨水，'x'表示沾墨水。
输出
对于每个测试点，输出TAK（是）或NIE（否）。
样例输入
2
3 4 4 2
xx..
.xx.
xx..
x.
.x
x.
..
2 2 2 2
xx
xx
.x
x.
样例输出
TAK
NIE
记下印章中x的相对位置
找最左上角的没有被印到的x 然后依次匹配印章 匹配到的地方用vis++记录
最后判断是x的地方vis是否等于1 是.的地方vis是否等于0
代码：
#include <bits/stdc++.h>
using namespace std;
int cnt;
const int maxn = 1005;
char Mp[maxn][maxn];
char Yz[maxn];
int vis[maxn][maxn];
int n,m,a,b;
struct node{
int x,y;
}book[maxn*maxn];
int op(int x,int y)
{
for(int i=1;i<cnt;i++){
int xx = x+book[i].x;
int yy = y+book[i].y;
if(xx>n||yy>m||xx<1||yy<1)
return 1;
else
vis[xx][yy]++;
}
return 0;
}
int pd()
{
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(Mp[i][j]=='x'&&vis[i][j]!=1){
return 0;
}
if(Mp[i][j]=='.'&&vis[i][j]!=0){
return 0;
}
}
}
return 1;
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
memset(vis,0,sizeof(vis));
scanf("%d%d%d%d",&n,&m,&a,&b);
for(int i=1;i<=n;i++)
scanf("%s",Mp[i]+1);
cnt = 0;
int inx,iny;
for(int i=1;i<=a;i++)
{
scanf("%s",Yz+1);
for(int j=1;j<=b;j++)
{
if(Yz[j]=='x'){
if(!cnt){
inx = i;
iny = j;
cnt++;
}
else{
book[cnt].x = i-inx;
book[cnt++].y = j-iny;
}
}
}
}
int flag = 0;
for(int i=1;i<=n;i++)
{
if(flag)
break;
for(int j=1;j<=m;j++)
{
if(Mp[i][j]=='x'&&!vis[i][j])
{
vis[i][j]++;
flag = op(i,j);
if(flag)
break;
}
}
}
if(flag)
{
printf("NIE
");
continue;
}
if(pd())
printf("TAK
");
else
printf("NIE
");
}
}