一些废话
夜深人静的夜晚,我开了这道题。看起来,完成它是一件轻而易举的事。我想了想,打开Dev-C++,开始写代码。
然而,那时的我还不知道,我踏入了深渊......
咳咳,中二病犯了,前面的文字请忽略。
思路
题目要求最少操作次数,显然,我们要使用BFS来求解。
对于每个节点,接下来有最多三个子节点,用函数模拟即可。
因为要求输出操作序列,所以需要存储每个节点的父节点。
细节
我们还需要对魔板进行去重操作来剪枝。
这是因为:
由于BFS的特性,当一个魔板第一次出现时,得到它所需要的操作次数是最少的;如果它出现了多次,那么与首次出现相比,它所需的操作次数更多。从该魔板出发还原成目标魔板时,如果从第一个魔板出发,所用的总次数最少;而多次出现的必然比首次出现的所用的总次数多。
因此通过去重操作进行剪枝是必要的,这会使原本MLE的程序AC(作者亲身经历)。
别忘了输出60个字符就要换行。
另外,当目标模板与初始模板一致时,需要直接输出0
,结束程序。文章来源:https://www.toymoban.com/news/detail-637387.html
实现
变量等命名不规范,望见谅。文章来源地址https://www.toymoban.com/news/detail-637387.html
#include <cstdio>
#define N 10000005
#define fot(x,y,z) for(int x=y;x<=z;x++)
#define tof(x,y,z) for(int x=y;x>=z;x--)
int bd[9],bb[9];
int b2[9];
int q[N][9];
int dep[N];
int list[N];
char stk[N];
int fa[N];
bool exis[16777216];
void swap(int &x,int &y)
{
int temp=x;
x=y;
y=temp;
}
void A()
{
fot(i,1,4)
swap(bd[i],bd[9-i]);
}
void B()
{
int f[2];
f[0]=bd[4];
f[1]=bd[5];
tof(i,3,1)
bd[i+1]=bd[i];
fot(i,6,8)
bd[i-1]=bd[i];
bd[1]=f[0];
bd[8]=f[1];
}
void C()
{
int temp=bd[2];
bd[2]=bd[7];
bd[7]=bd[6];
bd[6]=bd[3];
bd[3]=temp;
}
void setts(int i)
{
fot(j,1,8)
q[i][j]=bd[j];
}
void getts(int i)
{
fot(j,1,8)
bd[j]=q[i][j];
}
bool judge()
{
fot(i,1,8)
{
if(bd[i]!=b2[i])
return 0;
}
return 1;
}
void print(int x)
{
printf("%d\n",dep[x]);
int i;
for(i=1;x;i++)
{
stk[i]=list[x]-1+'A';
x=fa[x];
}
int cnt=0;
tof(j,i-1,1)
{
cnt++;
printf("%c",stk[j]);
if(cnt%60==0)
printf("\n");
}
}
bool exist()
{
int number=0;
fot(i,1,8)
number=number*8+bd[i]-1;
if(exis[number])
return 1;
else
{
exis[number]=1;
return 0;
}
}
int main()
{
fot(i,1,8)
scanf("%d",&b2[i]);
fot(i,1,8)
bd[i]=i;
if(judge())
{
printf("0");
return 0;
}
int head=0,tail=0;
setts(0);
fa[0]=-1;
while(head<=tail)
{
getts(head);
fot(i,1,3)
{
if(i==1) A();
if(i==2) B();
if(i==3) C();
if(exist())
{
getts(head);
continue;
}
tail++;
list[tail]=i;
fa[tail]=head;
setts(tail);
dep[tail]=dep[head]+1;
if(judge())
{
print(tail);
return 0;
}
getts(head);
}
head++;
}
}
到了这里,关于P2730 [USACO3.2] 魔板 Magic Squares 题解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!