自动搬运

查看原文

来自洛谷，原作者为

	Furina_Hate_Comma > 最后在线时间：2025年8月24日0时8分 < 由 exOIso 发送激光

搬运于2025-08-24 22:45:33，当前版本为作者最后更新于2023-04-22 14:25:33，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

一道大暴力。

话说 USACO 是不是和 CCF 学的赛时放那么恶心的题。

回归正题：

由于格子只会由白变黑，不会由黑变白。

所以直接枚举 4 个方向判断有没有不应该黑的格子黑了（注意不是错了因为后面还可以印）。

代码实现：

#include<bits/stdc++.h>
using namespace std;
#define neverTLE ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define reg register
#define endl '\n'
int t,n,k;
int main(){
	neverTLE;
	cin>>t;
	while(t--){
		cin>>n;
		char mp[30][30]={0},st[30][30]={0},bd[30][30]={0};
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				cin>>mp[i][j];
			}
		}
		cin>>k;
		for(int i=1;i<=k;i++){
			for(int j=1;j<=k;j++){
				cin>>st[i][j];
			}
		}
		
		for(int i=1;i+k-1<=n;i++){
			for(int j=1;j+k-1<=n;j++){
				bool flag=1;
				for(int ii=i,iii=1;ii<=i+k-1;ii++,iii++){
					for(int jj=j,jjj=1;jj<=j+k-1;jj++,jjj++){
						if(mp[ii][jj]!=st[iii][jjj]&&mp[ii][jj]=='.'){
							flag=0;
						}
					}
				}
				if(flag){
				for(int ii=i,iii=1;ii<=i+k-1;ii++,iii++){
					for(int jj=j,jjj=1;jj<=j+k-1;jj++,jjj++){
						if(bd[ii][jj]!='*')	bd[ii][jj]=st[iii][jjj];
					}
				}
				}
				flag=1;
				for(int ii=i,jjj=k;ii<=i+k-1;ii++,jjj--){
					for(int jj=j,iii=1;jj<=j+k-1;jj++,iii++){
						if(mp[ii][jj]!=st[iii][jjj]&&mp[ii][jj]=='.'){
							flag=0;
						}
					}
				}
				if(flag){
				for(int ii=i,jjj=k;ii<=i+k-1;ii++,jjj--){
					for(int jj=j,iii=1;jj<=j+k-1;jj++,iii++){
							if(bd[ii][jj]!='*')bd[ii][jj]=st[iii][jjj];
					}
				}
				}
				flag=1;
				for(int ii=i,iii=k;ii<=i+k-1;ii++,iii--){
					for(int jj=j,jjj=k;jj<=j+k-1;jj++,jjj--){
						if(mp[ii][jj]!=st[iii][jjj]&&mp[ii][jj]=='.'){
							flag=0;
						}
					}
				}
				if(flag){
				for(int ii=i,iii=k;ii<=i+k-1;ii++,iii--){
					for(int jj=j,jjj=k;jj<=j+k-1;jj++,jjj--){
						if(bd[ii][jj]!='*')	bd[ii][jj]=st[iii][jjj];
					}
				}
				}
				flag=1;
				for(int ii=i,jjj=1;ii<=i+k-1;ii++,jjj++){
					for(int jj=j,iii=k;jj<=j+k-1;jj++,iii--){
						if(mp[ii][jj]!=st[iii][jjj]&&mp[ii][jj]=='.'){
							flag=0;
						}
					}
				}
				if(flag){
				for(int ii=i,jjj=1;ii<=i+k-1;ii++,jjj++){
					for(int jj=j,iii=k;jj<=j+k-1;jj++,iii--){
						if(bd[ii][jj]!='*')	bd[ii][jj]=st[iii][jjj];
					}
				}
				}
			}
		}
		int flagg=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				if(bd[i][j]!=mp[i][j]&&mp[i][j]=='*'){
					flagg=1;
					goto jump;
				}
			}
		}
		jump:
		/*for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				cout<<bd[i][j]<<' ';
			}
			cout<<endl;
		}
		*/
		if(flagg){
			cout<<"NO"<<endl;
		}
		else{
			cout<<"YES"<<endl;
		}
	}
	return 0;
}