UVA810,A Dicey Problem

| OI

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");
    }
}