求助
查看原帖
求助
457016
zhouqiyue楼主2023/6/22 21:43

感觉代码除了康托展开的循坏和ac代码不大一样,不晓得哪里有问题,求助大佬

#include<bits/stdc++.h>
using namespace std;
int g,l,r;
int pre[50005],step[50005],b[1000000],t[10];
char f[50005];
int jc[10]={0,1,2,6,24,120,720,5040,40320,362880};
struct node
{
	int a[2][5];
}s[100000];
int turnd(node x)
{
	int tot;
	int sum=0;
	for(int i=1;i<=4;i++)
	t[i]=x.a[0][i];
	for(int i=3;i>=0;i--)
	t[8-i]=x.a[1][i+1];
	for(int i=1;i<8;i++)
	{
		tot=0;
		for(int j=i+1;j<=8;j++)
		if(t[i]>t[j])
		tot++;
		sum+=jc[8-i]*tot;
	}
	return sum;
}
node change(int l,int i)
{
	node temp;
	if(i==1)
	{
		temp.a [1][1]=s[l].a [0][1];
		temp.a [1][2]=s[l].a [0][2];
		temp.a [1][3]=s[l].a [0][3];
		temp.a [1][4]=s[l].a [0][4];
		temp.a [0][1]=s[l].a [1][1];
		temp.a [0][2]=s[l].a [1][2];
		temp.a [0][3]=s[l].a [1][3];
		temp.a [0][4]=s[l].a [1][4];
	}
	else if(i==2)
	{
		temp.a [0][1]=s[l].a [0][4];
		temp.a [0][2]=s[l].a [0][2];
		temp.a [0][3]=s[l].a [0][3];
		temp.a [0][4]=s[l].a [0][1];
		temp.a [1][1]=s[l].a [1][4];
		temp.a [1][2]=s[l].a [1][2];
		temp.a [1][3]=s[l].a [1][3];
		temp.a [1][4]=s[l].a [1][1];
	}
	else
	{
		temp.a [0][1]=s[l].a [0][1];
		temp.a [0][2]=s[l].a [1][2];
		temp.a [0][3]=s[l].a [0][2];
		temp.a [0][4]=s[l].a [0][4];
		temp.a [1][1]=s[l].a [1][1];
		temp.a [1][2]=s[l].a [1][3];
		temp.a [1][3]=s[l].a [0][3];
		temp.a [1][4]=s[l].a [1][4];
	}
	return temp;
}
void print(int i)
{
	if(i==1)
	return ;
	print(pre[i]);
	cout<<f[i];
}
void bfs()
{
	while(l<=r)
	{
		for(int i=1;i<=3;i++)
		{
			int x;
			node d=change(l,i);
			x=turnd(d);
			if(!b[x])
			{
				b[x]=1;
				s[++r]=d; 
				step[r]=step[l]+1;
				pre[r]=l;
				f[r]=char('A'+i-1);
				if(x==g)
			{
				cout<<step[r]<<endl;
				print(r);
				return ;
			}
			}
		}
		l++;
	}
}
int main()
{
	pre[1]=1;
	for(int i=1;i<=4;i++)
	s[1].a [0][i]=i;
	for(int i=1;i<=4;i++)
	s[1].a [1][i]=8-i+1;
	int h=turnd(s[1]);
	b[h]=1;
	r++;
	l++;
	node x;
	for(int i=1;i<=4;i++)
	cin>>x.a [0][i];
	for(int i=1;i<=4;i++)
	cin>>x.a [1][5-i];
	g=turnd(x);
	if(g==h)
	cout<<0<<endl;
	bfs();
	return 0;
}
2023/6/22 21:43
加载中...