Submission #51109572

---

Source Code Expand

// LUOGU_RID: 150146216
// LUOGU_RID: 150076734
// Author: gsczl71
// Copyright (c) 2024 gsczl71 All rights reserved.

#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fs first
#define sc second
#define endl '\n'
#define debug puts("AK IOI")
#define re register
#define pb push_back
#define mem(a,x) memset((a),(x),sizeof(a))
#define vi vector<int>
#define pq priority_queue
using namespace std;
//#define int long long
const int mod = 1e9+7;
//const int mod = 998244353;
const int inf = 0x3f3f3f3f,N = 7,M = 1e6+5,K = 3000+5;
const long long linf = 0x3f3f3f3f3f3f3f3f;
int a[N][N];
int vis[N][N];
int color[N][N];
int n;
int dx[4]={0,-1,0,1};
int dy[4]={1,0,-1,0};
pii js(int x){
	return {(x-1)/4+1,(x-1)%4+1};
}
void dfs(int x,int y,int col){
	for(int i = 0 ;i < 4;i++){
		int xx = x + dx[i];
		int yy = y + dy[i];
		if(xx >= 0 && xx <= 5 &&yy >= 0 &&yy <= 5 && (vis[xx][yy]^(col-1)) && !color[xx][yy]){
			color[xx][yy] = col;
			dfs(xx,yy,col);
		}
	}
}
void solve(){
	n=4;
	for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) cin >> a[i][j];
	
	int ans=0;
	for(int i = 1;i<=(1<<(n*n))-1;i++){
		int flag=1;
		for(int j = 1;j <= n * n ;j++){
			if(!((i>>(j-1))&1)&&a[js(j).fs][js(j).sc]) {
				flag=0;break;
			}vis[js(j).fs][js(j).sc] = (i>>(j-1))&1;
		}if(flag){
			// ans++;
			int col = 0;
			memset(color,0,sizeof color);
			int flag=1;
			for(int x = 1;x <= n && flag;x++){
				for(int y = 1;y <= n;y++){
					if(vis[x][y] && !col && !color[x][y]){
						color[x][y] = ++col;
						dfs(x,y,col);flag=0;break;
						
					}
				}
			}
			flag = 1;
			for(int x=0;x<=5 && flag;x++){
				for(int y=0;y<=5;y++){
					if(!vis[x][y] && col && !color[x][y]){
						color[x][y] = ++col;
						dfs(x,y,col);
						flag=0;
						break;
					}
				}
			}
			int ok = 1;
			for(int x = 0;x<=5;x++){
				for(int y = 0;y <= 5;y++){
					if(color[x][y] == 0){
						ok = 0;
						break;
					}
				}
			}
			if(ok) ans++;
		}
	}cout<<ans<<endl;
}
signed main(){
	// ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T=1;
//	cin >> T;
	while(T--) solve();
	return 0;
}

Submission Info

Judge Result