AcWing 1107. 魔板
原题链接
简单
作者:
ZTEG
,
2019-11-08 21:19:40
,
所有人可见
,
阅读 1935
思路十分简单,但是代码很长
#include<bits/stdc++.h>
using namespace std;
struct oppo{
int a[5][10];
int s;
queue<char> cz;//存怎么操作的
bool operator==(const oppo x)//重载 == 的判断
{
for(int i=1;i<=2;i++)
for(int j=1;j<=4;j++)
if(a[i][j]!=x.a[i][j])
return 0;
return 1;
}
}ans,st;
queue< oppo > v;
oppo xxx(oppo x)//交换上下两行
{
swap(x.a[1],x.a[2]);
x.s++;
x.cz.push('A');
return x;
}
oppo yyy(oppo x)//将最右边的一列插入到最左边
{
swap(x.a[1][1],x.a[1][4]);
swap(x.a[1][3],x.a[1][4]);
swap(x.a[1][2],x.a[1][3]);
swap(x.a[2][1],x.a[2][4]);
swap(x.a[2][3],x.a[2][4]);
swap(x.a[2][2],x.a[2][3]);
x.s++;
x.cz.push('B');
return x;
}
oppo zzz(oppo x)//魔板中央对的4个数作顺时针旋转
{
int y=x.a[1][2];
x.a[1][2]=x.a[2][2];
x.a[2][2]=x.a[2][3];
x.a[2][3]=x.a[1][3];
x.a[1][3]=y;
x.s++;
x.cz.push('C');
return x;
}
bool f[9][9][9][9][9][9][9][9];//记忆化
int main()
{
st.a[1][1]=1;st.a[1][2]=2;st.a[1][3]=3;st.a[1][4]=4;st.a[2][1]=8;st.a[2][2]=7;st.a[2][3]=6;st.a[2][4]=5;st.s=0;//初始化
for(int i=1;i<=4;i++)
cin>>ans.a[1][i];
for(int i=4;i>=1;i--)
cin>>ans.a[2][i];
v.push(st);
while(v.size())
{
oppo lxl=v.front();
v.pop();
if(lxl==ans)
{
cout<<lxl.s<<endl;
while(lxl.cz.size())
{
cout<<lxl.cz.front();
lxl.cz.pop();
}
return 0;
}
oppo to;
to=xxx(lxl);//A操作
if(!f[to.a[1][1]][to.a[1][2]][to.a[1][3]][to.a[1][4]][to.a[2][1]][to.a[2][2]][to.a[2][3]][to.a[2][4]])//判断是否走过
{
f[to.a[1][1]][to.a[1][2]][to.a[1][3]][to.a[1][4]][to.a[2][1]][to.a[2][2]][to.a[2][3]][to.a[2][4]]=1;//标记
v.push(to);
}
to=yyy(lxl);//B操作
if(!f[to.a[1][1]][to.a[1][2]][to.a[1][3]][to.a[1][4]][to.a[2][1]][to.a[2][2]][to.a[2][3]][to.a[2][4]])//判断是否走过
{
f[to.a[1][1]][to.a[1][2]][to.a[1][3]][to.a[1][4]][to.a[2][1]][to.a[2][2]][to.a[2][3]][to.a[2][4]]=1;//标记
v.push(to);
}
to=zzz(lxl);//C操作
if(!f[to.a[1][1]][to.a[1][2]][to.a[1][3]][to.a[1][4]][to.a[2][1]][to.a[2][2]][to.a[2][3]][to.a[2][4]])//判断是否走过
{
f[to.a[1][1]][to.a[1][2]][to.a[1][3]][to.a[1][4]][to.a[2][1]][to.a[2][2]][to.a[2][3]][to.a[2][4]]=1;//标记
v.push(to);
}
}
}
tql!!!!!!
tql!!!!!
tql!!!!
tql!!!