玄关求条
  • 板块P4997 不围棋
  • 楼主Fu_Tao
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/8/29 17:59
  • 上次更新2024/8/29 21:17:51
查看原帖
玄关求条
169736
Fu_Tao楼主2024/8/29 17:59
#define it <> ::iterator
#include <algorithm>
#include <iostream>
#include <iomanip>
#include <cstring>
#include <string>
#include <bitset>
#include <cstdio>
#include <vector>
#include <ctime>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
using namespace std;
typedef long long ll;//unsigned
const ll nex[4][2]={{0,1},{1,0},{0,-1},{-1,0}};
const ll inf=0x7fffffff;
const ll mod=1e9+7;//记得改scanf 
ll n,a[1000001],f[1000001],siz[1000001],book[1000001],flag;
ll col=1,lst[3]={0,1,1};
char c;
map<ll,ll> mp;
ll p(ll x,ll y){
	return (x-1)*n+y;
}
ll find(ll x){
	return f[x]==x?x:f[x]=find(f[x]);
}
void merge(ll x,ll y){
	ll fx=find(x),fy=find(y);
	if(fx==fy)return ;
	f[fx]=fy;
	siz[fy]+=siz[fx];
	siz[fx]=0;
	return ;
}
void init(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(!a[p(i,j)])continue ;
			for(int k=0;k<4;k++){
				ll dx=i+nex[k][0];
				ll dy=j+nex[k][1];
				if(dx<1||dy<1||dx>n||dy>n)continue ;
				if(!a[p(dx,dy)])siz[find(p(i,j))]++;
			}
			if(i!=1)if(a[p(i,j)]==a[p(i-1,j)])merge(p(i,j),p(i-1,j));
			if(j!=1)if(a[p(i,j)]==a[p(i,j-1)])merge(p(i,j),p(i,j-1));
		}
	}
	return ;
}
bool check(ll x,ll y,ll col){//下(x,y)处是否满足周围有气 
	ll sum=0,tot=0;
	mp.clear();
	for(int k=0;k<4;k++){
		ll dx=x+nex[k][0];
		ll dy=y+nex[k][1];
		if(dx<1||dy<1||dx>n||dy>n)continue ;
		if(!a[p(dx,dy)])sum++;//周围的气
		else if(a[p(dx,dy)]==col){//同色棋子 
			siz[find(p(dx,dy))]--;
		} 
		else if(a[p(dx,dy)]!=col){//异色的棋子 
			if(siz[find(p(dx,dy))]==1)return 0;//被堵死 
			siz[find(p(dx,dy))]--;
		}
	}
	for(int k=0;k<4;k++){
		ll dx=x+nex[k][0];
		ll dy=y+nex[k][1];
		if(dx<1||dy<1||dx>n||dy>n)continue ;
		if(col==a[p(dx,dy)]){//同色棋子 
			if(!mp.count(find(p(dx,dy))))tot+=siz[find(p(dx,dy))];//剩的气 
			mp[find(p(dx,dy))]=1;
		}
	}
	if(!sum&&!tot){//同色棋子无气 
		for(int k=0;k<4;k++){
			ll dx=x+nex[k][0];
			ll dy=y+nex[k][1];
			if(dx<1||dy<1||dx>n||dy>n)continue ;
			if(!a[p(dx,dy)])continue ; 
			siz[find(p(dx,dy))]++;//归还之前被占的气 
		}
		return 0;
	}
	siz[find(p(x,y))]+=sum;
	for(int k=0;k<4;k++){
		ll dx=x+nex[k][0];
		ll dy=y+nex[k][1];
		if(dx<1||dy<1||dx>n||dy>n)continue ;
		if(col==a[p(dx,dy)])merge(p(x,y),p(dx,dy));//合并同色棋子 
	}
	return 1;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			cin>>c;
			f[p(i,j)]=p(i,j);
			if(c=='.')continue ;
			book[p(i,j)]=1;
			if(c=='X')a[p(i,j)]=1;
			else if(c=='O')a[p(i,j)]=2;
		}
	}
	init();
	while(!flag&&lst[1]<n*n&&lst[2]<n*n){
		for(int pos=lst[col];pos<=n*n;pos++){
			if(book[pos])continue ;//有棋子了 
			ll x,y;
			if(pos%n==0){x=pos/n;y=n;}
			else {y=pos%n;x=(pos-y)/n+1;}
			if(pos==n*n&&!check(x,y,col)){
				flag=1;
				break;
			}
			if(check(x,y,col)){
				printf("%lld %lld\n",x,y);
				lst[col]=pos+1;
				book[pos]=1;
				a[pos]=col;
				break;
			}
//			for(int i=1;i<=n;i++){
//				for(int j=1;j<=n;j++){
//					cout<<siz[find(p(i,j))]<<" ";
//				}cout<<endl;
//			}
		}
		col^=3;
	}
	cout<<"-1 -1";
	return 0;
} 

记录

2024/8/29 17:59
加载中...