萌新刚学OI,阳历没过求条
查看原帖
萌新刚学OI,阳历没过求条
889917
limingyuan333楼主2024/10/2 16:23
#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[5][5];
bool check(){
	for(int i=1;i<=4;i++){
		if(a[i][1]==a[i][2]&&a[i][2]==a[i][3]&&a[i][3]==a[i][4])return 1;
		if(a[1][i]==a[2][i]&&a[2][i]==a[3][i]&&a[3][i]==a[4][i])	return 1;
	}
	if(a[1][1]==a[2][2]&&a[2][2]==a[3][3]&&a[3][3]==a[4][4])	return 1;
	if(a[4][1]==a[3][2]&&a[3][2]==a[2][3]&&a[2][3]==a[1][4])	return 1;
	return 0;
}
int dx[5]={-1,1,0,0};
int dy[5]={0,0,1,-1};
void iddfs(int x,int y,int xx,int yy,int depth,int id,int color){
	if(depth==id){
		if(check()){
			cout<<id;exit(0);
		}
		return ;
	}
	for(int i=0;i<4;i++){
		int nx=x+dx[i];
		int ny=y+dy[i];
		int nxx=xx+dx[i];
		int nyy=yy+dy[i];
		if(nx>=1&&nx<=4&&ny>=1&&ny<=4&&a[nx][ny]!=color){
			swap(a[nx][ny],a[x][y]);
			int colors=2;
			if(color==2)	colors=1;
			iddfs(nx,ny,xx,yy,depth+1,id,colors);
			swap(a[nx][ny],a[x][y]);
		}
		if(nxx>=1&&nxx<=4&&nyy>=1&&nyy<=4&&a[nxx][nyy]!=color){
			swap(a[nxx][nyy],a[xx][yy]);
			int colors=2;
			if(color==2)	colors=1;
			iddfs(x,y,nxx,nyy,depth+1,id,colors);
			swap(a[nxx][nyy],a[xx][yy]);
		}
	}
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(NULL),cout.tie(NULL);
	int fx1,fy1,fx2,fy2;
	for(int i=1;i<5;i++){
		for(int j=1;j<5;j++){
			char c;cin>>c;
			if(c=='B')	a[i][j]=1;
			if(c=='W')	a[i][j]=2;
			if(c=='O'&&(!fx1))	fx1=i,fy1=j;
			else if(c=='O')	fx2=i,fy2=j;
		}
	} 
	int dep=0;
	while(1){
		iddfs(fx1,fy1,fx2,fy2,0,dep,1);
		iddfs(fx1,fy1,fx2,fy2,0,dep,2);
		++dep;
	}
	return 0;
}
2024/10/2 16:23
加载中...