BFS。比较繁琐的就是骰子状态的变化表。然后有意思的是我输出了多余的\0
然后WA了好几次。。。检查输出时发现编辑器提示“二进制文件无法打开”。。
数据保证至多一个解。精妙啊。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <set>
#include <string>
#include <vector>
using namespace std;
const int maxstate = 1000000;
struct State
{
int x, y, front, top;
State(int _x = 0, int _y = 0, int _front = 0, int _top = 0)
{
x = _x;
y = _y;
front = _front;
top = _top;
}
bool operator<(const State &b) const
{
return (x - 1) * 1000 + (y - 1) * 100 + front * 10 + top <
(b.x - 1) * 1000 + (b.y - 1) * 100 + b.front * 10 + b.top;
}
};
State st[maxstate];
int fa[maxstate];
const int bk[] = {-1, 6, 5, 4, 3, 2, 1};
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
int roll[7][7] = {
{0},
{0, 0, 4, 2, 5, 3, 0},
{0, 3, 0, 6, 1, 0, 4},
{0, 5, 1, 0, 0, 6, 2},
{0, 2, 6, 0, 0, 1, 5},
// {0, 5, 1, 0, 0, 6, 2},
// {0, 3, 0, 6, 1, 0, 4},
{0, 4, 0, 1, 6, 0, 3},
// {0, 0, 4, 2, 5, 3, 0},
{0, 0, 3, 5, 2, 4, 0},
};
set<State> vis;
void init_look_table() { vis.clear(); }
int map[12][12];
void print(int start)
{
vector<int> v;
while (fa[start])
{
v.push_back(start);
start = fa[start];
}
v.push_back(start);
int j = 0;
for (int i = v.size() - 1; i >= 0; i--, j++)
{
if (!(j % 9))
cout<<endl<<" ";
printf("(%d,%d)%s", st[v[i]].x, st[v[i]].y, i ? "," : "");
// printf("(%d,%d)%c", st[v[i]].x, st[v[i]].y, i ? ',' : '\0');
// WA的原因。。。
}
}
bool try_to_insert(State &s){
if(vis.count(s))return false;
vis.insert(s);
return true;
}
void ps(State &s){
printf("x=%d,y=%d,front=%d,top=%d\n",s.x,s.y,s.front,s.top);
}
int main()
{
int kase=0;
while (1)
{
string maze;
cin >> maze;
if (maze == "END")
{
cout<<endl;
return 0;
}
if(kase++)printf("\n");
cout << maze;
int lx, ly;
State goal;
scanf("%d%d%d%d%d%d", &lx, &ly, &goal.x, &goal.y, &goal.top, &goal.front);
memset(map,0,sizeof map);
for (int i = 1; i <= lx; i++)
{
for (int j = 1; j <= ly; j++)
{
scanf("%d", &map[i][j]);
}
}
init_look_table();
memset(fa, 0, sizeof fa);
int frnt = 1, rear = 2;
memcpy(&st[1],&goal,sizeof goal);
bool flag=true;
while (frnt < rear)
{
State &s = st[frnt];
if (frnt != 1 && (goal.x==s.x) && (goal.y==s.y))
{
print(frnt);
flag=false;
break;
}
for (int d = 0; d < 4; d++)
{
State news;
news.x = s.x + dx[d];
news.y = s.y + dy[d];
switch (d)
{
case 1:
news.front = s.front;
news.top = roll[s.front][s.top];
break;
case 0:
news.front = s.front;
{
int t = s.top;
t = roll[s.front][t];
t = roll[s.front][t];
news.top = roll[s.front][t];
}
break;
case 2:
news.front = s.top;
news.top = 7 - s.front;
break;
case 3:
news.top = s.front;
news.front = 7 - s.top;
break;
default:
break;
}
if (news.x >= 1 && news.y >= 1 && news.x <= lx && news.y <= ly &&
((-1 == map[news.x][news.y]) || ((s.top) == map[news.x][news.y])))
{
if (try_to_insert(news))
{
fa[rear] = frnt;
st[rear++] = news;
}
}
}
frnt++;
}
if(flag)printf("\n No Solution Possible");
}
}