【题解】(PIE) ([POI2015]) ([P3585])
逼自己每天一道模拟题
传送门:(PIE) ([POI2015]) ([P3585])
【题目描述】
一张 (n*m) 的方格纸,有些格子需要印上墨水,剩下的格子需要保持干净。你有一个 (a*b) 的印章,有些格子有墨水的。你需要判断能否用这个印章满足要求。
但印的过程中需要满足以下要求:
((1))印章不可以旋转。
((2))不能把墨水印到纸外面。
((3))纸上的同一个格子不可以印多次。
【输入】
第一行一个整数 (q),表示测试点数量。接下来 (q) 个测试点,每个测试点中:第一行包含4个整数 (n,m,a,b)。接下来 (n) 行,每行 (m) 个字符,描述纸上的图案。('.') 表示留白,('x') 表示需要染黑。接下来 (a) 行,每行 (b) 个字符,描述印章。('.') 表示不沾墨水,('x') 表示沾墨水。
【输出】
对于每个测试点,输出 (TAK)(可满足)或 (NIE)(无法满足)。
【数据范围】
(100\%) (1 leqslant q leqslant 10) (,) (1 leqslant n,m,a,b leqslant 1000)
【分析】
炒鸡大水题
先用一个数组储存印章中每一个墨与最左上角墨的相对位置。
扫一遍纸张,一旦发现有需要印墨水的地方,就将其作为起始点扫一遍刚刚的数组,如果有矛盾则说明不满足。
注意要把题目看清楚,有三个要求,我一开始忘了第二条结果 (WA) 了三个点....
【Code】
#include<cstdio>
#define F(o,x,y) for(int o=x;o<=y;++o)
const int N=1005;
int T,n,m,a,b,t,nx,ny,stx,sty,wx[N*N],wy[N*N];char s[N][N],Q[N][N];
inline int judge(){
F(i,1,n)F(j,1,m)
if(Q[i][j]=='x')
F(k,1,t){
nx=i+wx[k],ny=j+wy[k];
if(nx>n||ny>m||Q[nx][ny]=='.')return 0;
Q[nx][ny]='.';
}
return 1;
}
int main(){
scanf("%d",&T);
while(T--){
stx=sty=t=0;
scanf("%d%d%d%d",&n,&m,&a,&b);
F(i,1,n)scanf("%s",Q[i]+1);
F(i,1,a){
scanf("%s",s[i]+1);
F(j,1,b)
if(s[i][j]=='x'){
if(!stx)wx[++t]=0,wy[t]=0,stx=i,sty=j;
else wx[++t]=i-stx,wy[t]=j-sty;
}
}
puts(judge()?"TAK":"NIE");
}
}