bzoj3750 [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

正解：模拟。

如果每次找没有被覆盖的最左上的黑点，然后拿整个矩形去覆盖，复杂度就是错的。

但是我们只要把印章上黑点的位置拿出来去覆盖就行了，只要发现不合法就直接退出。

因为每个点最多只会被覆盖两次，所以复杂度是对的。

 1 #include <bits/stdc++.h>
 2 #define il inline
 3 #define RG register
 4 #define ll long long
 5 
 6 using namespace std;
 7 
 8 struct data{ int x,y; }st[1000010];
 9 
10 int vis[1010][1010],g[1010][1010],n,m,a,b,top;
11 
12 il int gi(){
13   RG int x=0,q=1; RG char ch=getchar();
14   while ((ch<'0' || ch>'9') && ch!='-') ch=getchar();
15   if (ch=='-') q=-1,ch=getchar();
16   while (ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar();
17   return q*x;
18 }
19 
20 il char gc(){
21   RG char ch=getchar();
22   while (ch!='.' && ch!='x') ch=getchar(); return ch;
23 }
24 
25 il void work(){
26   n=gi(),m=gi(),a=gi(),b=gi(),top=0;
27   for (RG int i=1;i<=n;++i)
28     for (RG int j=1;j<=m;++j) g[i][j]=gc()=='x',vis[i][j]=0;
29   for (RG int i=1;i<=a;++i)
30     for (RG int j=1;j<=b;++j) if (gc()=='x') st[++top]=(data){i,j};
31   for (RG int i=top;i;--i) st[i].x-=st[1].x,st[i].y-=st[1].y;
32   for (RG int i=1;i<=n;++i)
33     for (RG int j=1;j<=m;++j){
34       if (!g[i][j] || vis[i][j]) continue;
35       for (RG int k=1,X,Y;k<=top;++k){
36     X=i+st[k].x,Y=j+st[k].y;
37     if (X<=0 || X>n || Y<=0 || Y>m || vis[X][Y] || !g[X][Y]){ puts("NIE"); return; }
38     vis[X][Y]=1;
39       }
40     }
41   puts("TAK"); return;
42 }
43 
44 int main(){
45 #ifndef ONLINE_JUDGE
46   freopen("pieczec.in","r",stdin);
47   freopen("pieczec.out","w",stdout);
48 #endif
49   RG int T=gi();
50   while (T--) work();
51   return 0;
52 }