WA#2求助 玄关
查看原帖
WA#2求助 玄关
1047605
ZBXAMZL楼主2024/3/28 11:31
#include<iostream>
#include<cstdio>
#include<queue>
#include<map>
using namespace std;
struct node{
	string s;
	int pos[2],color;
	node(){}
	node(string a,int b,int c,int d){
		s=a,pos[0]=b,pos[1]=c,color=d;
	}
};
int ans=0x3f3f3f3f;
queue<node>q;
map<string,int>mp[2];
string st;
bool calc(node x){
	string y=x.s;
	for(int i=0;i<4;i++){
		if(y[i]==y[i+4]&&y[i+4]==y[i+8]&&y[i+8]==y[i+12])return 1;
		if(y[i]==y[i+1]&&y[i+1]==y[i+2]&&y[i+2]==y[i+3])return 1;
	}
	if(y[0]==y[5]&&y[5]==y[10]&&y[10]==y[15])return 1;
	if(y[3]==y[6]&&y[6]==y[9]&&y[9]==y[12])return 1;
	return 0;
}
void Left(string x,int pos1,int pos2,int color){
	string y=x;
	if((pos1+1)%4==0)return;
	if(y[pos1+1]=='B'&&color==0)return;
	else if(y[pos1+1]=='W'&&color==1)return;
	swap(y[pos1+1],y[pos1]);
	pos1++;
	if(mp[1-color][y])return;
	q.push(node(y,pos1,pos2,1-color));
	mp[1-color][y]=mp[color][x]+1;
}
void Right(string x,int pos1,int pos2,int color){
	string y=x;
	if(pos1%4==0)return;
	if(y[pos1-1]=='B'&&color==0)return;
	else if(y[pos1-1]=='W'&&color==1)return;
	swap(y[pos1-1],y[pos1]);
	pos1--;
	if(mp[1-color][y])return;
	q.push(node(y,pos1,pos2,1-color));
	mp[1-color][y]=mp[color][x]+1;
}
void Up(string x,int pos1,int pos2,int color){
	string y=x;
	if(pos1>=12)return;
	if(y[pos1+4]=='B'&&color==0)return;
	else if(y[pos1+4]=='W'&&color==1)return;
	swap(y[pos1+4],y[pos1]);
	pos1+=4;
	if(mp[1-color][y])return;
	q.push(node(y,pos1,pos2,1-color));
	mp[1-color][y]=mp[color][x]+1;
}
void Down(string x,int pos1,int pos2,int color){
	string y=x;
	if(pos1<=3)return;
	if(y[pos1-4]=='B'&&color==0)return;
	else if(y[pos1-4]=='W'&&color==1)return;
	swap(y[pos1-4],y[pos1]);
	pos1-=4;
	if(mp[1-color][y])return;
	q.push(node(y,pos1,pos2,1-color));
	mp[1-color][y]=mp[color][x]+1;
}
void bfs(string s,int pos1,int pos2,int color){
	mp[0].clear();mp[1].clear();
	while(!q.empty())q.pop();
	q.push(node(s,pos1,pos2,color));
	mp[color][s]=0;
	while(!q.empty()){
		node x=q.front();
		q.pop();
		if(calc(x)){
			ans=min(ans,mp[x.color][x.s]);
			return;
		}
		Left(x.s,x.pos[0],x.pos[1],x.color);
		Left(x.s,x.pos[1],x.pos[0],x.color);
		Right(x.s,x.pos[0],x.pos[1],x.color);
		Right(x.s,x.pos[1],x.pos[0],x.color);
		Up(x.s,x.pos[0],x.pos[1],x.color);
		Up(x.s,x.pos[1],x.pos[0],x.color);
		Down(x.s,x.pos[0],x.pos[1],x.color);
		Down(x.s,x.pos[1],x.pos[0],x.color);
		}
}
int main(){
	int t1=0,t2=0;
	string t;
	for(int i=0;i<4;i++){
		cin>>t;
		st+=t;
		for(int j=0;j<4;j++)
			if(t[j]=='O'&&t1==0)t1=j+i*4;
			else if(t[j]=='O')t2=j+i*4;
	}
	bfs(st,t1,t2,0);//0代表白色 
	bfs(st,t1,t2,1);//1代表黑色 
	cout<<ans<<endl;
	return 0;
}
2024/3/28 11:31
加载中...