求助 abc322 D
  • 板块灌水区
  • 楼主2c_s
  • 当前回复0
  • 已保存回复0
  • 发布时间2023/10/1 14:09
  • 上次更新2023/11/2 16:47:43
查看原帖
求助 abc322 D
583186
2c_s楼主2023/10/1 14:09

WA*2

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define pf push_front
#define pob pop_back
#define pof pop_front
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define pil pair<int,ll>
#define fi first
#define se second
using namespace std;
inline ll read(){
	ll k=0,flag=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-')flag=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		k=(k<<1)+(k<<3)+(c^48);
		c=getchar();
	}
	return k*flag;
}
inline void print(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    ll y=10,len=1;
    while(y<=x){
        y=(y<<1)+(y<<3);
        len++;
    }
    while(len--){
        y/=10;
        putchar(x/y+48);
        x%=y;
    }
}
inline char readc(){
	char c=getchar();
	while(c=='\n'||c==' ')c=getchar();
	return c;
}
const int N=20;
int n,g[N][N],ans,res[N][N];
struct node{
	int r,c,mp[N][N];
	bool use;
}a[N];
inline void era(node &k){
	bool flag=1;
	while(1){
		for(int i=1;i<=k.r;++i){
			if(k.mp[i][1])flag=0;
		}
		if(!flag)break;
		for(int i=1;i<=k.r;++i){
			for(int j=2;j<=k.c;++j){
				k.mp[i][j-1]=k.mp[i][j];
			}
		}
		for(int i=1;i<=k.r;++i)k.mp[i][k.c]=0;
		k.c--;
	}
	flag=1;
	while(1){
		for(int i=1;i<=k.c;++i){
			if(k.mp[1][i])flag=0;
		}			
		if(!flag)break;
		for(int i=2;i<=k.r;++i){
			for(int j=1;j<=k.c;++j){
				k.mp[i-1][j]=k.mp[i][j];
			}
		}
		for(int i=1;i<=k.c;++i)k.mp[k.r][i]=0;
		k.r--;
	}
	flag=1;
	while(1){
		for(int i=1;i<=k.r;++i){
			if(k.mp[i][k.c])flag=0;
		}
		if(!flag)break;
		k.c--;
	}
	flag=1;
	while(1){
		for(int i=1;i<=k.c;++i){
			if(k.mp[k.r][i])flag=0;
		}
		if(!flag)break;
		k.r--;
	}
	return ;
}
inline void change(node &k){
	k.r=4,k.c=4;
	for(int i=1;i<=k.r;++i){
		for(int j=1;j<=k.c;++j)res[i][j]=k.mp[i][j];
	}
	for(int i=1;i<=k.r;++i){
		for(int j=1;j<=k.c;++j){
			k.mp[i][j]=res[k.c-j+1][i];
		}
	}
	era(k);
	return ;
}
inline bool check(node k,int i,int j,int id){
	for(int op=1;op<=4;++op){
		bool flag=1;
		for(int x=1;x<=k.r;++x){
			if(x+i-1>4){
				flag=0;
				break;
			}
			for(int y=1;y<=k.c;++y){
				if(y+j-1>4){
					flag=0;
					break;
				}
				if(g[i+x-1][j+y-1]!=0&&k.mp[x][y]==1){
					flag=0;
					break;
				}
			}
			if(!flag)break;
		}
		if(flag){
			for(int x=1;x<=k.r;++x){
				for(int y=1;y<=k.c;++y){
					if(!g[i+x-1][j+y-1]&&k.mp[x][y])g[i+x-1][y+j-1]=id;
				}
			}
			return 1;
		}
		change(k);
	}
	return 0;
}
inline void del(int id){
	for(int i=1;i<=4;++i){
		for(int j=1;j<=4;++j){
			if(g[i][j]==id)g[i][j]=0;
		}
	}
	return ;
}
inline void dfs(int cnt){
//	for(int i=1;i<=4;++i){
//		for(int j=1;j<=4;++j){
//			cout<<g[i][j];
//		}
//		cout<<"\n";
//	}
//	for(int i=1;i<=n;++i)cout<<a[i].use<<" ";
//	cout<<cnt<<" "<<ans;
//	cout<<"\n\n";
	if(ans==1)return ;
	if(cnt==n){
		int ok=1;
		for(int i=1;i<=4;++i){
			for(int j=1;j<=4;++j){
				if(!g[i][j])ok=0;
			}
		}
		ans+=ok;
		if(ok)return ;
	}
	for(int p=1;p<=n;++p){
		if(a[p].use)continue;
		for(int i=1;i<=4-a[p].r+1;++i){
			for(int j=1;j<=4-a[p].c+1;++j){
				if(check(a[p],i,j,p)){
					a[p].use=1;
					dfs(cnt+1);
					a[p].use=0;
					del(p);
				}
			}
		}
	}
	return ;
}
int main(){
	n=3;
	for(int k=1;k<=n;++k){
		a[k].r=4,a[k].c=4;
		for(int i=1;i<=a[k].r;++i){
			for(int j=1;j<=a[k].c;++j){
				char c;
				cin>>c;
				if(c=='#')a[k].mp[i][j]=1;
			}
		}
		era(a[k]);
//		for(int i=1;i<=4;++i){
//			for(int j=1;j<=4;++j){
//				cout<<a[k].mp[i][j];
//			}
//			cout<<"\n";
//		}
//		cout<<"\n";
	}
	dfs(0);
	if(!ans)puts("No");
	else puts("Yes");
	return 0;
}
2023/10/1 14:09
加载中...