Zoj3059， 使用顶面，前面描述骰子状态，预处理得到骰子滚动的转化，使用bfs查找，使用visited保存检查过的状态，以剪枝。

// Zoj3059.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include <deque>
#include <iostream>
#include <set>
using namespace std;
struct Status
{
int x;
int y;
int t;
int n;
bool operator==(Status&lo)
{
return x==lo.x && y == lo.y && t == lo.t && n == lo.n;
}
bool operator<(const Status&lo)const
{
return (x+y)< (lo.x+lo.y);
}
friend ostream& operator<<(ostream&,const Status&);

};
template <typename T>
class StatusLess : public less<T>
{
public:
virtual bool operator()(const T& t1, const T& t2) const
{
return t1< t2;
}
};
set<Status,StatusLess<Status>> visited;
int cube[7][4] = {{0,0,0,0},
{2,3,5,6},
{1,6,4,3},
{1,2,4,5},
{2,6,5,3},
{1,3,4,6},
{1,5,4,2}
};
int getLeftFace(int top, int north)
{
for (int ii = 0; ii< 4;ii++)
{
if (cube[top][ii]==north)
return cube[top][(ii+3)%4];
}
return -1;
}
int getRightFace(int top, int north)
{
for(int ii = 0; ii < 4; ii++)
{
if (cube[top][ii]==north)
return cube[top][(ii+1)%4];
}
return -1;
}
int getBottomFace(int top, int )
{
int bottom = top + 3;
return bottom > 6 ? bottom%6: bottom;
}
int getBackFace(int , int north)
{
int south = north + 3;
return south > 6 ? south%6: south;
}
ostream& operator <<(ostream& out, Status& lo)
{
out << "(" << lo.x <<","<< lo.y<<") " << "(" <<lo.t <<","<<lo.n <<")";
return out;
}
Status roll(int orient, Status& original)//left 0, right 1, front 2, back 3
{
Status result;
switch(orient)
{
case 0:
{
result.x = original.x-1;
result.y = original.y;
result.t = getRightFace(original.t, original.n);
result.n = original.n;
break;
}
case 1:
{
result.x = original.x+1;
result.y = original.y;
result.t = getLeftFace(original.t, original.n);
result.n = original.n;
break;
}
case 2:
{
result.x = original.x;
result.y = original.y+1;
result.t = getBackFace(original.t, original.n);
result.n = original.t;
break;
}
case 3:
{
result.x = original.x;
result.y = original.y-1;
result.t = original.n;
result.n = getBottomFace(original.t, original.n);
break;
}
default: break;
}
return result;
}
deque<Status> queue;
void bfs(Status& start, Status& end)
{
while(!queue.empty())
{
Status now = queue.front();
if (visited.find(now)!= visited.end())
{
queue.pop_front();
continue;
}
visited.insert(now);
queue.pop_front();
for (int ii = 0; ii < 4; ii++)
{
Status newS = roll(ii,now);
cout << now << " " << ii << " " << newS << endl;
queue.push_back(newS);
if (newS == end)
{
return;
}
}
}
}
int _tmain(int argc, _TCHAR* argv[])
{
Status start,end;
start.x = 0;
start.y = 0;
start.t = 1;
start.n = 2;
end.x = 1;
end.y = 1;
end.t = 5;
end.n = 6;

queue.push_back(start);
bfs(start,end);
return 0;
}