首页 > 代码库 > bzoj3750 [POI2015]Piecz??
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
贪心：对于当前某一个状态，一定要用印章的左上角来和最左上的那个点匹配
然后变模拟了
#include<cstdio>#include<iostream>#include<cstring>#define LL long longusing namespace std;inline LL read(){ LL x=0,f=1;char ch=getchar(); while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();} while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();} return x*f;}int T,n,m,a,b,cnt;bool map[1010][1010];bool mrk[1010][1010];int colx[1000010],coly[1000010];inline bool paint(int x,int y){ for (int i=1;i<=cnt;i++) { int nx=x+colx[i],ny=y+coly[i]; if (nx<1||ny<1||nx>n||ny>m||!mrk[nx][ny])return 1; mrk[nx][ny]=0; } return 0;}inline void work(){ n=read();m=read(); a=read();b=read(); for(int i=1;i<=n;i++) for (int j=1;j<=m;j++) { char ch=getchar();while (ch!=‘x‘&&ch!=‘.‘)ch=getchar(); mrk[i][j]=map[i][j]=(ch==‘x‘); } cnt=0; for (int i=1;i<=a;i++) for (int j=1;j<=b;j++) { char ch=getchar();while (ch!=‘x‘&&ch!=‘.‘)ch=getchar(); if (ch==‘x‘) { colx[++cnt]=i; coly[cnt]=j; } } if (cnt==0) { printf("NIE\n"); return; } int rex=colx[1],rey=coly[1]; for (int i=1;i<=cnt;i++) { colx[i]-=rex; coly[i]-=rey; } for(int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (mrk[i][j]) { if (paint(i,j)) { printf("NIE\n"); return; } } printf("TAK\n");}int main(){ T=read(); while (T--)work();}
bzoj3750 [POI2015]Piecz??
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。