【NOJ1325】【算法实验三】【分支限界法】特殊的二阶魔方
1325.特殊的二阶魔方
时限：1000ms 内存限制：10000K 总时限：3000ms
描述
魔方大家应该都玩过。现在有一个特殊的二阶魔方，它只有一面是白色，其余五个面全是黑色。玩这个魔方当然也有特殊的规则，玩家只能通过六种方式去改变它，底层向左转一格（称为DL），底层向右转一格（称为DR），右侧向上转一格（称为RU），右侧向下转一格（称为RD），内侧顺时针转一格（称为C），内侧逆时针转一格（称为CC）。现给一魔方的状态，请在最少的步骤内把魔方还原
输入
按照上下左右前后的顺序给出各面的具体情况，0表示白色，1表示黑色。上下、左右、前后分别是以俯视图、左视图、正视图看到的
输出
输出令一面全为白色的最小步数。
#include <iostream>
#include <queue>
using namespace std;
struct node
{
int cube[6][4]; //六个面，每面四块
//面的顺序为上下左右前后
int num[6]; //六个面，每个面进行二进制编码，再转换成十进制存在num数组中
};
queue <node> q1;
int step[16][16][16][16][16][16]; //存储到达这一状态的步数
int used[16][16][16][16][16][16]; //判重数组
int bfs(); //深搜
node setnum(node n1); //计算num数组的值
bool canmoveto(node n1, node n2); //对n2节点进行判重
//若重复，直接返回false
//若不重复，则标记used数组，更新step数组
node moveto(node n1, int d); //返回n1状态经由d操作之后获得的新状态
bool eqtarget(node n1); //判断是否到达目标状态
int main()
{
node start;
for(int i=0; i<6; i++)
{
for(int j=0; j<4; j++)
{
start.cube[i][j]=cin.get()-'0'; //将字符转成数字
if(j==1)cin.get(); //吃掉回车符
}
cin.get(); //吃掉回车符
}
start=setnum(start); //计算start节点的num数组
/*
for(int i=0; i<4; i++)
cout<<start.cube[1][i]<<' ';
cout<<endl;
for(int i=0; i<6; i++)
cout<<start.num[i]<<' ';
cout<<endl;
*/
if(eqtarget(start)) //一开始就到达目标状态
{
cout<<'0'<<endl;
}
else
{
q1.push(start); //入队
//初始步数为0
step[start.num[0]][start.num[1]][start.num[2]][start.num[3]][start.num[4]][start.num[5]]=0;
//标记初始状态用过
used[start.num[0]][start.num[1]][start.num[2]][start.num[3]][start.num[4]][start.num[5]]=1;
//开始广搜
cout<<bfs()<<endl;
}
return 0;
}
int bfs()
{
node top,next;
while(!q1.empty())
{
top=q1.front();
q1.pop();
for(int i=0; i<6; i++) //六种操作
{
next=moveto(top, i); //经过i操作，获得新的next状态
if(canmoveto(top, next)) //对next状态进行判重，不重复就更新used数组和step数组
{
if(eqtarget(next)) //达到目标状态就返回步数
{
return step[next.num[0]][next.num[1]][next.num[2]][next.num[3]][next.num[4]][next.num[5]];
}
else //没达到目标状态就入队，等待下次pop扩展
{
q1.push(next);
}
}
}
}
return -1; //如果没搜到，返回-1
}
//计算n1节点的num数组
node setnum(node n1)
{
for(int i=0; i<6; i++) //六个面
{
n1.num[i]=0; //清空num
for(int j=0; j<4; j++) //每面4块，0==白，1==黑，当作4位二进制编码
{
n1.num[i]*=2; //把4位二进制编码转换成十进制，范围应是0-15
n1.num[i]+=n1.cube[i][j];
}
}
return n1; //返回填充了num数组的n1节点
}
//判断n2节点是否重复
bool canmoveto(node n1, node n2)
{
if(used[n2.num[0]][n2.num[1]][n2.num[2]][n2.num[3]][n2.num[4]][n2.num[5]]==1)
{
return false; //如果重复就返回false
}
else //如果没重复就更新
{
//更新used数组，记录n2节点用过
used[n2.num[0]][n2.num[1]][n2.num[2]][n2.num[3]][n2.num[4]][n2.num[5]]=1;
//更新step数组，到达n2节点所用步数=1+到达n1节点所用步数
step[n2.num[0]][n2.num[1]][n2.num[2]][n2.num[3]][n2.num[4]][n2.num[5]]=
1+step[n1.num[0]][n1.num[1]][n1.num[2]][n1.num[3]][n1.num[4]][n1.num[5]];
//返回true表示不重复
return true;
}
}
//对n1进行六种操作
node moveto(node n1, int d)
{
node n2; //新建一个节点
for(int i=0; i<6; i++)
{
for(int j=0; j<4; j++)
{
n2.cube[i][j]=n1.cube[i][j]; //先复制一下n1的各面情况
}
}
switch(d)
{
case 0: //底层向左转一格（DL）
{
n2.cube[2][2]=n1.cube[4][2]; //左面的2、3块=前面的2、3块
n2.cube[2][3]=n1.cube[4][3];
n2.cube[4][2]=n1.cube[3][3]; //前面的2、3块=右面的3、2块
n2.cube[4][3]=n1.cube[3][2];
n2.cube[3][2]=n1.cube[5][2]; //右面的3、2块=后面的2、3块
n2.cube[3][3]=n1.cube[5][3];
n2.cube[5][2]=n1.cube[2][3]; //后面的2、3块=左面的3、2块
n2.cube[5][3]=n1.cube[2][2];
n2.cube[1][1]=n1.cube[1][0]; //下面的4个块顺时针转
n2.cube[1][0]=n1.cube[1][2];
n2.cube[1][2]=n1.cube[1][3];
n2.cube[1][3]=n1.cube[1][1];
break;
}
case 1: //底层向右转一格（DR）
{
n2.cube[3][2]=n1.cube[4][3]; //右面的2、3块=前面的3、2块
n2.cube[3][3]=n1.cube[4][2];
n2.cube[4][2]=n1.cube[2][2]; //前面的2、3块=左面的2、3块
n2.cube[4][3]=n1.cube[2][3];
n2.cube[2][2]=n1.cube[5][3]; //左面的2、3块=后面的3、2块
n2.cube[2][3]=n1.cube[5][2];
n2.cube[5][2]=n1.cube[3][2]; //后面的3、2块=右面的2、3块
n2.cube[5][3]=n1.cube[3][3];
n2.cube[1][2]=n1.cube[1][0]; //下面的4个块逆时针转
n2.cube[1][3]=n1.cube[1][2];
n2.cube[1][1]=n1.cube[1][3];
n2.cube[1][0]=n1.cube[1][1];
break;
}
case 2: //右侧向上转一格（RU）
{
n2.cube[0][1]=n1.cube[4][1]; //上面的1、3块=前面的1、3块
n2.cube[0][3]=n1.cube[4][3];
n2.cube[4][1]=n1.cube[1][3]; //前面的1、3块=下面的3、1块
n2.cube[4][3]=n1.cube[1][1];
n2.cube[1][1]=n1.cube[5][1]; //下面的1、3块=后面的1、3块
n2.cube[1][3]=n1.cube[5][3];
n2.cube[5][1]=n1.cube[0][3]; //后面的1、3块=上面的3、1块
n2.cube[5][3]=n1.cube[0][1];
n2.cube[3][0]=n1.cube[3][1]; //右面的4个块逆时针转
n2.cube[3][1]=n1.cube[3][3];
n2.cube[3][3]=n1.cube[3][2];
n2.cube[3][2]=n1.cube[3][0];
break;
}
case 3: //右侧向下转一格（RD）
{
n2.cube[0][1]=n1.cube[5][3]; //上面的1、3块=后面的3、1块
n2.cube[0][3]=n1.cube[5][1];
n2.cube[5][1]=n1.cube[1][1]; //后面的1、3块=下面的1、3块
n2.cube[5][3]=n1.cube[1][3];
n2.cube[1][1]=n1.cube[4][3]; //下面的1、3块=前面的3、1块
n2.cube[1][3]=n1.cube[4][1];
n2.cube[4][1]=n1.cube[0][1]; //前面的1、3块=上面的1、3块
n2.cube[4][3]=n1.cube[0][3];
n2.cube[3][0]=n1.cube[3][2]; //右面的4个块顺时针转
n2.cube[3][2]=n1.cube[3][3];
n2.cube[3][3]=n1.cube[3][1];
n2.cube[3][1]=n1.cube[3][0];
break;
}
case 4: //内侧顺时针转一格（C）
{
n2.cube[0][2]=n1.cube[2][3]; //上面的2、3块=左面的3、1块
n2.cube[0][3]=n1.cube[2][1];
n2.cube[2][1]=n1.cube[1][2]; //左面的1、3块=下面的2、3块
n2.cube[2][3]=n1.cube[1][3];
n2.cube[1][2]=n1.cube[3][3]; //下面的2、3块=右面的3、1块
n2.cube[1][3]=n1.cube[3][1];
n2.cube[3][1]=n1.cube[0][2]; //右面的1、3块=上面的2、3块
n2.cube[3][3]=n1.cube[0][3];
n2.cube[4][0]=n1.cube[4][2]; //内侧的4个块顺时针转
n2.cube[4][2]=n1.cube[4][3];
n2.cube[4][3]=n1.cube[4][1];
n2.cube[4][1]=n1.cube[4][0];
break;
}
case 5: //内侧逆时针转一格（CC）
{
n2.cube[0][2]=n1.cube[3][1]; //上面的2、3块=右面的1、3块
n2.cube[0][3]=n1.cube[3][3];
n2.cube[3][1]=n1.cube[1][3]; //右面的1、3块=下面的3、2块
n2.cube[3][3]=n1.cube[1][2];
n2.cube[1][2]=n1.cube[2][1]; //下面的2、3块=左面的1、3块
n2.cube[1][3]=n1.cube[2][3];
n2.cube[2][1]=n1.cube[0][3]; //左面的1、3块=上面的3、2块
n2.cube[2][3]=n1.cube[0][2];
n2.cube[4][0]=n1.cube[4][1]; //内侧的4个块逆时针转
n2.cube[4][1]=n1.cube[4][3];
n2.cube[4][3]=n1.cube[4][2];
n2.cube[4][2]=n1.cube[4][0];
break;
}
}
/*
cout<<d<<endl;
for(int i=0; i<6; i++)
{
for(int j=0; j<4; j++)
{
cout<<n2.cube[i][j]<<' ';
}
cout<<endl;
}
*/
//计算新状态n2的num数组
n2=setnum(n2);
return n2;
}
//判断n1节点是否到达目标状态
bool eqtarget(node n1)
{
for(int i=0; i<6; i++)
{
if(n1.num[i]==0) //目标状态为一面有四个白块，二进制编码为0000，换算成十进制为0
{
return true; //6个面里只要有一个面为0就返回true
}
}
return false;
}
啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊我AC了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
想让全世界知道我AC了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
这破题我踏马的写了两个多小时了啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊啊
凌晨零点二十四了，纪念一下写过的最恶心的代码，明天来补注释QAAAAAAAAAAAQ
【后记】
1.对于一道广搜，套路相似，不同的是：如何表示状态，如何转换状态，如何判重。
2.下图解释我如何用 cube [6] [4] 表示魔方的状态。
这里要注意：人的眼睛和魔方的位置是不变的，“后面-5”的正视图，相当于无视“前面-4”的遮挡，把魔方当作透明的，直接透视到后面，而不是把魔方转180度看到的“后面-5”，左视图、俯视图如上。
一共有六种操作，按题中出现的顺序编码0，1，2，3，4，5，在图中标出，请配合moveto(node n1, int d)函数代码食用。
（虽然每面的变换又长又罗嗦不想看，但我写的时候也很崩溃啊orz）
以下是moveto(node n1, int d)函数代码，d代表六种操作编码
//对n1进行六种操作
node moveto(node n1, int d)
{
node n2; //新建一个节点
for(int i=0; i<6; i++)
{
for(int j=0; j<4; j++)
{
n2.cube[i][j]=n1.cube[i][j]; //先复制一下n1的各面情况
}
}
switch(d)
{
case 0: //底层向左转一格（DL）
{
n2.cube[2][2]=n1.cube[4][2]; //左面的2、3块=前面的2、3块
n2.cube[2][3]=n1.cube[4][3];
n2.cube[4][2]=n1.cube[3][3]; //前面的2、3块=右面的3、2块
n2.cube[4][3]=n1.cube[3][2];
n2.cube[3][2]=n1.cube[5][2]; //右面的3、2块=后面的2、3块
n2.cube[3][3]=n1.cube[5][3];
n2.cube[5][2]=n1.cube[2][3]; //后面的2、3块=左面的3、2块
n2.cube[5][3]=n1.cube[2][2];
n2.cube[1][1]=n1.cube[1][0]; //下面的4个块顺时针转
n2.cube[1][0]=n1.cube[1][2];
n2.cube[1][2]=n1.cube[1][3];
n2.cube[1][3]=n1.cube[1][1];
break;
}
case 1: //底层向右转一格（DR）
{
n2.cube[3][2]=n1.cube[4][3]; //右面的2、3块=前面的3、2块
n2.cube[3][3]=n1.cube[4][2];
n2.cube[4][2]=n1.cube[2][2]; //前面的2、3块=左面的2、3块
n2.cube[4][3]=n1.cube[2][3];
n2.cube[2][2]=n1.cube[5][3]; //左面的2、3块=后面的3、2块
n2.cube[2][3]=n1.cube[5][2];
n2.cube[5][2]=n1.cube[3][2]; //后面的3、2块=右面的2、3块
n2.cube[5][3]=n1.cube[3][3];
n2.cube[1][2]=n1.cube[1][0]; //下面的4个块逆时针转
n2.cube[1][3]=n1.cube[1][2];
n2.cube[1][1]=n1.cube[1][3];
n2.cube[1][0]=n1.cube[1][1];
break;
}
case 2: //右侧向上转一格（RU）
{
n2.cube[0][1]=n1.cube[4][1]; //上面的1、3块=前面的1、3块
n2.cube[0][3]=n1.cube[4][3];
n2.cube[4][1]=n1.cube[1][3]; //前面的1、3块=下面的3、1块
n2.cube[4][3]=n1.cube[1][1];
n2.cube[1][1]=n1.cube[5][1]; //下面的1、3块=后面的1、3块
n2.cube[1][3]=n1.cube[5][3];
n2.cube[5][1]=n1.cube[0][3]; //后面的1、3块=上面的3、1块
n2.cube[5][3]=n1.cube[0][1];
n2.cube[3][0]=n1.cube[3][1]; //右面的4个块逆时针转
n2.cube[3][1]=n1.cube[3][3];
n2.cube[3][3]=n1.cube[3][2];
n2.cube[3][2]=n1.cube[3][0];
break;
}
case 3: //右侧向下转一格（RD）
{
n2.cube[0][1]=n1.cube[5][3]; //上面的1、3块=后面的3、1块
n2.cube[0][3]=n1.cube[5][1];
n2.cube[5][1]=n1.cube[1][1]; //后面的1、3块=下面的1、3块
n2.cube[5][3]=n1.cube[1][3];
n2.cube[1][1]=n1.cube[4][3]; //下面的1、3块=前面的3、1块
n2.cube[1][3]=n1.cube[4][1];
n2.cube[4][1]=n1.cube[0][1]; //前面的1、3块=上面的1、3块
n2.cube[4][3]=n1.cube[0][3];
n2.cube[3][0]=n1.cube[3][2]; //右面的4个块顺时针转
n2.cube[3][2]=n1.cube[3][3];
n2.cube[3][3]=n1.cube[3][1];
n2.cube[3][1]=n1.cube[3][0];
break;
}
case 4: //内侧顺时针转一格（C）
{
n2.cube[0][2]=n1.cube[2][3]; //上面的2、3块=左面的3、1块
n2.cube[0][3]=n1.cube[2][1];
n2.cube[2][1]=n1.cube[1][2]; //左面的1、3块=下面的2、3块
n2.cube[2][3]=n1.cube[1][3];
n2.cube[1][2]=n1.cube[3][3]; //下面的2、3块=右面的3、1块
n2.cube[1][3]=n1.cube[3][1];
n2.cube[3][1]=n1.cube[0][2]; //右面的1、3块=上面的2、3块
n2.cube[3][3]=n1.cube[0][3];
n2.cube[4][0]=n1.cube[4][2]; //内侧的4个块顺时针转
n2.cube[4][2]=n1.cube[4][3];
n2.cube[4][3]=n1.cube[4][1];
n2.cube[4][1]=n1.cube[4][0];
break;
}
case 5: //内侧逆时针转一格（CC）
{
n2.cube[0][2]=n1.cube[3][1]; //上面的2、3块=右面的1、3块
n2.cube[0][3]=n1.cube[3][3];
n2.cube[3][1]=n1.cube[1][3]; //右面的1、3块=下面的3、2块
n2.cube[3][3]=n1.cube[1][2];
n2.cube[1][2]=n1.cube[2][1]; //下面的2、3块=左面的1、3块
n2.cube[1][3]=n1.cube[2][3];
n2.cube[2][1]=n1.cube[0][3]; //左面的1、3块=上面的3、2块
n2.cube[2][3]=n1.cube[0][2];
n2.cube[4][0]=n1.cube[4][1]; //内侧的4个块逆时针转
n2.cube[4][1]=n1.cube[4][3];
n2.cube[4][3]=n1.cube[4][2];
n2.cube[4][2]=n1.cube[4][0];
break;
}
}
//计算新状态n2的num数组
n2=setnum(n2);
return n2;
}
3.以下是每面的二进制-十进制编码表示示意图
由此可以解释判重数组used[16][16][16][16][16][16]和存储步数数组step[16][16][16][16][16][16]的由来，六维表示六个面，每一维最大值是15，表示全黑面1111的十进制编码15
也可以解释eqtarget函数，如果某一面的十进制编码为0，证明二进制编码是0000，也就是全白
上图配合下面的setnum(node n1)食用，int num[6]数组存储了每面的十进制编码：
struct node
{
int cube[6][4]; //六个面，每面四块
//面的顺序为上下左右前后
int num[6]; //六个面，每个面进行二进制编码，再转换成十进制存在num数组中
};
//中间代码省略
//计算n1节点的num数组
node setnum(node n1)
{
for(int i=0; i<6; i++) //六个面
{
n1.num[i]=0; //清空num
for(int j=0; j<4; j++) //每面4块，0==白，1==黑，当作4位二进制编码
{
n1.num[i]*=2; //把4位二进制编码转换成十进制，范围应是0-15
n1.num[i]+=n1.cube[i][j];
}
}