2015年2月15日 星期日

2015/02/15 vijos P1016 北京2008的挂钟 (IOI1994)

/*
    簡單BFS
*/
// https://vijos.org/p/1016
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

#define INF 1e9

string s[] = {"ABDE","ABC","BCEF","ADG","BDEFH","CFI","DEGH","GHI","EFHI"};
int A[9];

int dis[1<<18];
int from[1<<18];
int FA[1<<18];

deque<int> Ans;

int turn(int x, int i)
{
    int t = 3<<(2*i);
    int p = (x&t)>>(2*i);
    p = (p+1)%4;


    return x-(x&t)+(p<<(2*i));
}

int main()
{
    int now = 0;

    for(int i = 0; i < 9; i++)
        scanf("%d", &A[i]);

    for(int i = 8; i >= 0; i--)
        now<<=2, now|=A[i];

    fill(dis, dis+(1<<18), INF);

    queue<int> que;
    dis[now] = 0;
    que.push(now);

    while( !que.empty() )
    {
        int F = que.front();
        que.pop();

        for(int i = 0; i < 9; i++)
        {
            int x = F;

            for(int si = 0; si < s[i].size(); si++)
                x = turn(x, s[i][si]-'A');

            if( dis[x] == INF )
            {
                dis[x] = dis[F]+1;
                que.push(x);
                from[x] = i+1;
                FA[x] = F;
            }
        }
    }

    int p = 0;

    while(1)
    {
        if( p == now ) break;
        Ans.push_back(from[p] );
        p = FA[p];
    }

    for(int i = Ans.size()-1; i >= 0; i--)
    {
        printf("%d", Ans[i]);

        if( i ) printf(" ");
        else puts("");
    }
}

沒有留言:

張貼留言