直接贪心模拟即可,对于每个点,如果它未被覆盖,直接在这覆盖一次。
每个黑点只会被扫一次,所以总复杂度为 \(\mathcal O\rm (nm)\)
Code
%: pragma GCC optimize("O9")
%: pragma GCC optimize("inline")
#include<bits/stdc++.h>
#define ri register signed
#define p(i) ++i
using namespace std;
namespace IO{
char buf[1<<21],*p1=buf,*p2=buf,OPUT[100];
#define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?(-1):*p1++;
template<typename T>inline void read(T &x) {
ri f=1;x=0;register char ch=getchar();
while(!isdigit(ch)) {if (ch=='-') f=0;ch=getchar();}
while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
x=f?x:-x;
}
template<typename T>inline void print(T x,char t) {
if (x<0) putchar('-'),x=-x;
if (!x) return putchar('0'),(void)putchar(t);
ri cnt(0);
while(x) OPUT[p(cnt)]=x%10,x/=10;
for (ri i(cnt);i;--i) putchar(OPUT[i]^48);
return (void)putchar(t);
}
}
using IO::read;using IO::print;
namespace nanfeng{
#define node(x,y) (node){x,y}
#define FI FILE *IN
#define FO FILE *OUT
template<typename T>inline T cmax(T x,T y) {return x>y?x:y;}
template<typename T>inline T cmin(T x,T y) {return x>y?y:x;}
static const int N=1e3+7;
char s[N];
int mt[N][N],mxx,mxy,mn,cnt,T,n,m,a,b,fg;
struct node{int x,y;}pnt[N*N];
inline int check(int x,int y) {
for (ri i(1);i<=cnt;p(i)) {
int cx=x+pnt[i].x,cy=y+pnt[i].y;
if (cx<1||cx>n||cy<1||cy>m) return 0;
if (!mt[cx][cy]) return 0;
mt[cx][cy]=0;
}
return 1;
}
inline int main() {
//FI=freopen("nanfeng.in","r",stdin);
//FO=freopen("nanfeng.out","w",stdout);
read(T);
for (ri z(1);z<=T;p(z)) {
read(n),read(m),read(a),read(b);
cnt=fg=0;
mxx=INT_MAX,mxy=INT_MAX;
for (ri i(1);i<=n;p(i)) {
scanf("%s",s+1);
for (ri j(1);j<=m;p(j)) mt[i][j]=(s[j]=='x');
}
for (ri i(1);i<=a;p(i)) {
scanf("%s",s+1);
for (ri j(1);j<=b;p(j))
if (s[j]=='x') {
pnt[p(cnt)]=node(i,j);
if (i<mxx) mxx=i,mxy=j,mn=cnt;
else if (i==mxx) if (j<mxy) mxy=j,mn=cnt;
}
}
if (!cnt) {puts("No");continue;}
for (ri i(1);i<=cnt;p(i)) {
if (mn==i) continue;
pnt[i].x-=pnt[mn].x,pnt[i].y-=pnt[mn].y;
}
pnt[mn].x=pnt[mn].y=0;
for (ri i(1);i<=n&&!fg;p(i))
for (ri j(1);j<=m&&!fg;p(j))
if (mt[i][j]) if (!check(i,j)) fg=1,puts("No");
if (fg) continue;
puts("Yes");
}
return 0;
}
}
int main() {return nanfeng::main();}
手机扫一扫
移动阅读更方便
你可能感兴趣的文章