求助
查看原帖
求助
636442
yangyang1000楼主2023/2/16 21:00
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

struct node
{
	int a[5][5];
	int space_x[5],space_y[5];
	int step;
	int who;
};

queue<node> q;

bool check(node x)
{
	for(int i=1;i<=4;i++)
	{
		if(x.a[i][1] == 0 && x.a[i][2] == 0 && x.a[i][3] == 0 && x.a[i][4] == 0) return true;
		if(x.a[i][1] == 1 && x.a[i][2] == 1 && x.a[i][3] == 1 && x.a[i][4] == 1) return true;
		if(x.a[1][i] == 0 && x.a[2][i] == 0 && x.a[3][i] == 0 && x.a[4][i] == 0) return true;
		if(x.a[1][i] == 1 && x.a[2][i] == 1 && x.a[3][i] == 1 && x.a[4][i] == 1) return true;
	}
	if(x.a[1][1] == 0 && x.a[2][2] == 0 && x.a[3][3] == 0 && x.a[4][4] == 0) return true;
	if(x.a[1][1] == 1 && x.a[2][2] == 1 && x.a[3][3] == 1 && x.a[4][4] == 1) return true;
	if(x.a[1][4] == 0 && x.a[2][3] == 0 && x.a[3][2] == 0 && x.a[4][1] == 0) return true;
	if(x.a[1][4] == 1 && x.a[2][3] == 1 && x.a[3][2] == 1 && x.a[4][1] == 1) return true;
	return false;
}

void place_swap(int &a,int &b)
{
	a ^= b;
	b ^= a;
	a ^= b;
	return ;
}

int bfs()
{
	while(!q.empty())
	{
		node now = q.front();
		q.pop();
		
		if(check(now)) return now.step;
		
		for(int o=1;o<=2;o++)
		{
			int x = now.space_x[o],y = now.space_y[o];
			for(int i=0;i<4;i++)
			{
				int xnew = x + dx[i],ynew = y + dy[i];
				if(xnew < 1 || xnew > 4 || ynew < 1 || ynew > 4 || now.a[xnew][ynew] == 2 || now.a[xnew][ynew] == now.who) continue;
				
				
				node next = now;
				place_swap(next.a[x][y],next.a[xnew][ynew]);
				
				next.space_x[o] = xnew;
				next.space_y[o] = ynew;
				
				next.who ^= 1;
				next.step++;
				
				q.push(next);
			}
		}
	}
	return -1;
} 

int main()
{
	node start;
	bool flag = false;
	
	start.step = 0;
	for(int i=1;i<=4;i++)
	{
		string s;
		
		cin >> s;
		s = " " + s;
		
		for(int j=1;j<=4;j++)
		{
			if(s[j] == 'B') start.a[i][j] = 1;
			if(s[j] == 'W') start.a[i][j] = 0;
			if(s[j] == 'O')
			{
				start.a[i][j] = 2;
				if(flag == false)
				{
					start.space_x[1] = i;
					start.space_y[1] = j;
				}
				else
				{
					start.space_x[2] = i;
					start.space_y[2] = j;
				}
			}
		}
	}
	
	start.who = 0;
	q.push(start);
	start.who = 1;
	q.push(start);
	
	int ans = bfs();
	printf("%d",ans);
	return 0;
}

WA on #1,#2,#5。

2023/2/16 21:00
加载中...