「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.
3 4 4 2
xx..
.xx.
xx..
x.
.x
x.
..
2 2 2 2
xx
xx
.x
x.
Sample Output
TAK
NIE
NIE
题解
每次选择左上角的没有沾的然后和印章左上角配在一起沾一下。。。
把纸和印章的x都用链表串起来就能把复杂度降为n^2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<cstdio> #include<cmath> #include<cstring> #include<iostream> #define ll unsigned long long using namespace std; inline int read() { int x=0;char ch=getchar(); while(ch>'9'||ch<'0')ch=getchar(); while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x; } int T,n,m,a,b,cnt,top; int mp[1005][1005],qx[1000005],qy[1000005],xx[1000005],yy[1000005]; char ch[1005]; bool check(int x,int y) { for(int i=1;i<=cnt;i++) { int tx=x+xx[i],ty=y+yy[i]; if(tx>n||ty>m||tx<1||ty<1)return 0; if(!mp[tx][ty])return 0; else mp[tx][ty]=0; } return 1; } int main() { T=read(); while(T--) { memset(mp,0,sizeof(mp)); n=read();m=read();a=read();b=read(); cnt=top=0; for(int i=1;i<=n;i++) { scanf("%s",ch+1); for(int j=1;j<=m;j++) if(ch[j]=='x') { top++;qx[top]=i;qy[top]=j; mp[i][j]=top; } } int tx,ty; for(int i=1;i<=a;i++) { scanf("%s",ch+1); for(int j=1;j<=b;j++) if(ch[j]=='x') { if(!cnt)tx=i,ty=j; cnt++; xx[cnt]=i-tx,yy[cnt]=j-ty; } } bool flag=0; for(int i=1;i<=top;i++) if(mp[qx[i]][qy[i]]) if(!check(qx[i],qy[i])) { puts("NIE");flag=1;break; } if(!flag)puts("TAK"); } return 0; } |
Subscribe
计数器 9786919
OI 课件=>
OI 课件=>