Vexoben
Feb 9, 2018
题目链接：http://poj.org/problem?id=3131
题意
给你八个正方体，放于九宫格内，每个正方体相对面同色。每次可以将一个正方体翻滚到相邻空位，求使从高处向下看为给定的目标状态的最小移动次数。如果30步内不能到达判定无解。
题解
三维八数码问题，明显是一道搜索题。
先考虑状态数：空位有9种位置，每个正方体有6种放置方法，共15116544种状态。如果只有一组数据的话广搜就可以直接搜过去。
那么可以考虑双向广搜。显然末状态有256种可能。我们可以考虑从初状态搜20层，从末状态搜索10层，取交汇点即可。
但是还有一种更高妙的做法：深搜！
这个是在别人的博客上看到的。当时很惊讶深搜+估价函数（不在目标位置的格子数-1）居然可以过，就把代码拖下来跑了一发，对于15组全部无解的数据，开O2后在学校电脑上只跑了6s。
考虑不加估价函数时的状态数：由于不会往回走，即便在中间也最多有3种方案可以选择。但状态总数并不是3^30，而是从中心走到旁边，再走到角落，走到旁边，再走回中心，这样一次循环（走4步）的方案数只有321*2=12种，也就是即便跑满状态数也不会超过286654464种，而事实上并不会每次走回旁边后直接走到中心（可能又走到角落），再加上估价函数的剪枝，状态数又远小于这个数字 ！
最后在POJ上跑出来是1157MS，虽不及双向广搜，但也是十分理想的算法了。
#pragma GCC optimize(2)
#include<cstdio>
#include<utility>
using namespace std;
char s[3];
int x,y,H,ans,goal[5][5];
pair<int,int> a[5][5]; //a[i][j].first 为向上的一面，second为向前的一面
void Init() {
H=0; ans=31;
for (int i=1;i<=3;i++)
for (int j=1;j<=3;j++) {
scanf("%s",s+1);
if (s[1]=='E') goal[i][j]=0;
else if (s[1]=='W') goal[i][j]=1;
else if (s[1]=='R') goal[i][j]=2;
else goal[i][j]=3;
if (i==x&&j==y) a[i][j]=make_pair(0,0);
else a[i][j]=make_pair(1,2);
}
for (int i=1;i<=3;i++)
for (int j=1;j<=3;j++)
if (a[i][j].first!=goal[i][j])
H++; // 估价函数
}
void dfs(int tim,int las) {
if (tim+H-1>=ans) return;
if (!H) return (void) (ans=tim);
if (y>1&&las!=1) { // 从左边翻
pair<int,int> u=a[x][y],v=a[x][y-1];
a[x][y]=make_pair(6-a[x][y-1].first-a[x][y-1].second,a[x][y-1].second);
a[x][y-1]=make_pair(0,0);
int del=(goal[x][y]==a[x][y].first)+(goal[x][y-1]==a[x][y-1].first)-(goal[x][y]==u.first)-(goal[x][y-1]==v.first);
H-=del; y--; dfs(tim+1,0); H+=del; y++;
a[x][y]=u; a[x][y-1]=v;
}
if (y<3&&las!=0) { // 从右边翻
pair<int,int> u=a[x][y],v=a[x][y+1];
a[x][y]=make_pair(6-a[x][y+1].first-a[x][y+1].second,a[x][y+1].second);
a[x][y+1]=make_pair(0,0);
int del=(goal[x][y]==a[x][y].first)+(goal[x][y+1]==a[x][y+1].first)-(goal[x][y]==u.first)-(goal[x][y+1]==v.first);
H-=del; y++; dfs(tim+1,1); H+=del; y--;
a[x][y]=u; a[x][y+1]=v;
}
if (x>1&&las!=3) { // 从上面翻
pair<int,int> u=a[x][y],v=a[x-1][y];
a[x][y]=make_pair(a[x-1][y].second,a[x-1][y].first);
a[x-1][y]=make_pair(0,0);
int del=(goal[x][y]==a[x][y].first)+(goal[x-1][y]==a[x-1][y].first)-(goal[x][y]==u.first)-(goal[x-1][y]==v.first);
H-=del; x--; dfs(tim+1,2); H+=del; x++;
a[x][y]=u; a[x-1][y]=v;
}
if (x<3&&las!=2) { // 从下面翻
pair<int,int> u=a[x][y],v=a[x+1][y];
a[x][y]=make_pair(a[x+1][y].second,a[x+1][y].first);
a[x+1][y]=make_pair(0,0);
int del=(goal[x][y]==a[x][y].first)+(goal[x+1][y]==a[x+1][y].first)-(goal[x][y]==u.first)-(goal[x+1][y]==v.first);
H-=del; x++; dfs(tim+1,3); H+=del; x--;
a[x][y]=u; a[x+1][y]=v;
}
}
int main() {
while (scanf("%d%d",&y,&x)&&(x+y)) {
Init();
dfs(0,-1);
if (ans<=30) printf("%d\n",ans);
else puts("-1");
}
}