发现好像没有什么好做法,那就模拟么=。=
以印章左上角的'x'为基准,记录印章上'x'的相对位置模拟。记录相对位置是因为可能有这种情况↓
直接模拟是会漏掉的=。=
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=,M=;
int mapp[M][M],pos[N*N][];
int n,m,a,b,T,cnt,firx,firy;
char rd[N];
inline void i207M()
{
cnt=,firx=firy=-;
memset(mapp,,sizeof mapp);
}
inline bool judge()
{
register int i,j;
for(i=;i<=n;i++)
for(j=;j<=m;j++)
if(mapp[i][j]) return false;
return true;
}
inline bool print(int x,int y)
{
register int i;
for(i=;i<=cnt;i++)
{
int nx=x+pos[i][],ny=y+pos[i][];
if(!mapp[nx][ny]) return false;
if(nx>n||ny>m) return false;
mapp[nx][ny]=;
}
return true;
}
int main ()
{
register int i,j;
scanf("%d",&T);
while(T--)
{
i207M();
scanf("%d%d%d%d",&n,&m,&a,&b);
for(i=;i<=n;i++)
{
scanf("%s",rd+);
for(j=;j<=m;j++)
mapp[i][j]=(rd[j]=='x');
}
for(i=;i<=a;i++)
{
scanf("%s",rd+);
for(j=;j<=b;j++)
if(rd[j]=='x')
{
if(firx==-) firx=i,firy=j;
pos[++cnt][]=i-firx,pos[cnt][]=j-firy;
}
}
if(firx==-&&!judge()) {printf("NIE\n"); continue;}
bool f=true;
for(i=;i<=n&&f;i++)
for(j=;j<=m&&f;j++)
if(mapp[i][j]&&!print(i,j)) f=false;
(f&&judge())?printf("TAK\n"):printf("NIE\n");
}
return ;
}