wa34求调
查看原帖
wa34求调
1558713
yujunchen楼主2025/7/3 10:18
#include<bits/stdc++.h>
using namespace std;
int ne[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int x,y;
int a[4][4];
struct node{
	int arr[4][4];
	int color,step;
}t;
queue<node>q;
int ans=0;
bool check(node f)//判断合法解 
{
    for(int i=0;i<4;i++)
    {
        if(f.arr[i][0]==f.arr[i][1]&&f.arr[i][0]==f.arr[i][2]&&f.arr[i][0]==f.arr[i][3])return true;
        if(f.arr[0][i]==f.arr[1][i]&&f.arr[0][i]==f.arr[2][i]&&f.arr[0][i]==f.arr[3][i])return true;
    }
    if(f.arr[0][0]==f.arr[1][1]&&f.arr[0][0]==f.arr[2][2]&&f.arr[1][1]==f.arr[3][3])return true; 
    if(f.arr[0][3]==f.arr[2][1]&&f.arr[0][3]==f.arr[1][2]&&f.arr[1][3]==f.arr[3][1])return true;
    return false;
}
void bfs()
{
    while(q.size())
    {
        node n=q.front();
        q.pop();
        if(check(n))
        {
            ans=n.step;
            return;
            
        }
        for(int i=0;i<4;i++)
	        for(int j=0;j<4;j++)
	        {
	            if(n.arr[i][j]==0)
	            {
	            	int x=i,y=j;
	                for(int k=0;k<4;k++)
	                {
	                    int tx=x+ne[k][0];
	                    int ty=y+ne[k][1];
	                    if(tx>=0&&tx<4&&ty>=0&&ty<4&&n.arr[tx][ty]!=0&&n.arr[tx][ty]!=n.color)
	                    {
	                        node nn=n;//替换 
	                        swap(nn.arr[x][y],nn.arr[tx][ty]);
	                        if(n.color==1) nn.color=2;
	                        if(n.color==2) nn.color=1;
							nn.step=n.step+1;
	                        q.push(nn);
	                    }
	                }
	            }
	        }
    }
}
char c;
int main()
{
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 	for(int i=0;i<4;i++)
 		for(int j=0;j<4;j++)
 		{
 			cin>>c;
 			if(c=='B')t.arr[i][j]=1;
 			else if(c=='W')t.arr[i][j]=2;
 				else t.arr[i][j]=0;
		}
	if(check(t))
	{
		cout<<"0";
		return 0;
	}
	//开始判断初始化 
	for(int i=0;i<4;i++)
	{
		for(int j=0;j<4;j++)
		{
			if(t.arr[i][j]==0)
			{
				x=i;y=j;
				for(int k=0;k<4;k++)
				{
					int tx=x+ne[i][0];
					int ty=y+ne[i][1];
					if(tx<4&&ty<4&&tx>=0&&ty>=0&&t.arr[tx][ty]!=0)
					{
						node t1=t;
						swap(t1.arr[x][y],t1.arr[tx][ty]);
						t1.color=t1.arr[tx][ty];
						t1.step=1;
						q.push(t1);
				        
					}
				}
			}
		}
	}//初始化完成
	bfs(); 
	cout<<ans;
	return 0;
}

2025/7/3 10:18
加载中...