【题解】PIE [POI2015] [P3585]

【题解】(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");
    }
}
原文地址:https://www.cnblogs.com/Xing-Ling/p/10940602.html