poj 1077 Eight(双方向bfs)

タイトルリンク:http://poj.org/problem?id=1077
 
構想分析:テーマは最短の移動経路を探し出して、与えられた状態から最終状態に達することを要求する.
<1>探索アルゴリズム選択:最短の移動経路を見つける必要があるためbfs探索を選択
＜2＞判定方法:
スペースを数字9と見なすと、状態の集合を1-9の配列の組み合わせの集合と見なすことができ、康托展開に基づいて、各状態を正の整数にマッピングすることができる.
ハッシュテーブルで重み付けを行います.
<3>ステータス圧縮:検索時に各ステータスを1～9からなる9桁の数字に変換することで、ステータス圧縮と解凍を行うことができます.
<4>双方向広さ優先検索のテクニック:
1)利点:初期状態とターゲット状態が与えられた問題に対して、双方向検索を使用して検索することができ、空間と時間を節約することができる.
2)双方向広さ優先探索の考え方:双方向広さ優先探索は同時に2種類の探索を開始する;1つの広さ優先探索は、所与の状態からターゲット状態へ探索し、もう1つの広さ優先探索は、ターゲット状態から
指定されたステータスを検索すると、2つのステータスツリーが生成されます.検索時に各ステータスツリーの親ノードと子ノードの関係を記録します.各ステートツリーのルートノードからノードの拡張を開始すると、
のノードが既にステータスツリーに表示されている場合、ノードは拡張されません.拡張されたノードが別のステータスツリーにすでに存在する場合、最初のステータスとターゲットステータス(最短かどうか)を接続するパスが見つかります.
ある状態ツリーには初期状態とその状態との間に1つのパスが存在し、別の状態ツリーにはその状態とターゲット状態との間に1つのパスが存在するため、拡張ノードを接続点とし、
2本のステータスツリーの初期ステータスとターゲットステータスが接続されています. 
 
コードは次のとおりです.

#include <iostream>
#include <cstring>
#include <cmath>
using namespace std;

const int MAX_N = 362880 + 10; // 10! + 10
int set[MAX_N];                //     ，    ，           (0:     1:     2:    )
int map[9];                    //       
char path[MAX_N];              //           
const int FACT[9] = {1, 1, 2, 6, 24, 120, 720, 5040, 40320};
const int MOVE[4][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0}};

struct Node
{
    int state_num;
    int pre, next;            //             
    char pre_dir, next_dir;   //                 
}state_queue[MAX_N];

int Canto()
{
    int state_num = 1;
    for (int i = 0; i < 9; ++i)
    {
        int temp = map[i] - 1;

        for (int j = 0; j < i; ++j)
            temp -= (map[j] < map[i]);
        state_num += temp * FACT[8 - i];
    }
    return state_num;
}

void StateNumToMAP(int num)
{
    int i = 8;
    while (num)
    {
        map[i--] = num % 10;
        num /= 10;
    }
}

char MoveDirection(bool forward, int i)
{
    char result = 0;

    if (!forward)
    {
        if (0 <= i && i <= 1)
            i = 1 - i;
        else
            i = 5 - i;
    }

    switch (i)
    {
    case 0: result = 'u'; break;
    case 1: result = 'd'; break;
    case 2: result = 'l'; break;
    case 3: result = 'r'; break;
    }
    return result;
}

int MapToStateNum()
{
    int ans = 0;

    for (int i = 0; i < 9; ++i)
        ans = ans * 10 + map[i];
    return ans;
}

int BFS()
{
    int head, tail, state_canto_val;
    Node start, end;

    head = tail = 1;
    start.state_num = MapToStateNum();
    start.pre = -1;      // -1，      
    start.pre_dir = -1;  //   
    start.next = 0;      // 0      
    start.next_dir = 0;  //   
    state_canto_val = Canto();
    set[state_canto_val] = 1;

    if (start.state_num == 123456789)
        return -2;

    end.state_num = 123456789;
    end.next = -1;      // -1      
    end.next_dir = -1;  //   
    end.pre = 0;        // 0      
    end.pre_dir = 0;    //   

    state_queue[tail++] = start;
    state_queue[tail++] = end;
    set[1] = -2;

    while (head < tail)
    {
        int now_x, now_y, next_x, next_y;
        Node now_state;

        now_state = state_queue[head];
        StateNumToMAP(now_state.state_num);
        state_canto_val = Canto();

        for (int i = 0; i < 9; ++i)
        {
            if (map[i] == 9)
            {
                now_x = i % 3, now_y = i / 3;
                break;
            }
        }
        for (int i = 0; i < 4; ++i)
        {
            int temp_swap;
            Node next_state;

            next_x = now_x;
            next_y = now_y;
            next_x += MOVE[i][0];
            next_y += MOVE[i][1];

            if (next_x < 0 || next_x >= 3
                || next_y < 0 || next_y >= 3)
                continue;
            temp_swap = map[now_x + now_y * 3];
            map[now_x + now_y * 3] = map[next_x + next_y * 3];
            map[next_x + next_y * 3] = temp_swap;

            state_canto_val = Canto();
            if (state_queue[head].pre == 0 && set[state_canto_val] == 0)
            {
                set[state_canto_val] = -tail;
                next_state.state_num = MapToStateNum();
                next_state.pre = 0;
                next_state.pre_dir = 0;
                next_state.next = head;
                next_state.next_dir = MoveDirection(false, i);
                state_queue[tail++] = next_state;
            }
            else if (state_queue[head].pre == 0 && set[state_canto_val] > 0)
            {
                state_queue[abs(set[state_canto_val])].next = head;
                state_queue[abs(set[state_canto_val])].next_dir = MoveDirection(false, i);
                return abs(set[state_canto_val]);
            }
            else if (state_queue[head].next == 0 && set[state_canto_val] == 0)
            {
                set[state_canto_val] = tail;
                next_state.state_num = MapToStateNum();
                next_state.pre = head;
                next_state.pre_dir = MoveDirection(true, i);
                next_state.next = 0;
                next_state.next_dir = 0;
                state_queue[tail++] = next_state;
            }
            else if (state_queue[head].next == 0 && set[state_canto_val] < 0)
            {
                state_queue[abs(set[state_canto_val])].pre = head;
                state_queue[abs(set[state_canto_val])].pre_dir = MoveDirection(true, i);
                return abs(set[state_canto_val]);
            }

            temp_swap = map[now_x + now_y * 3];
            map[now_x + now_y * 3] = map[next_x + next_y * 3];
            map[next_x + next_y * 3] = temp_swap;
        }
        head++;
    }
    return -1;
}

void PrintPath(int id)
{
    int pos = 0;
    int temp_id = id;

    while (state_queue[temp_id].pre != -1)
    {
        path[pos++] = state_queue[temp_id].pre_dir;
        temp_id = state_queue[temp_id].pre;
    }

    for (int i = pos - 1; i >= 0; --i)
        printf("%c", path[i]);

    temp_id = id;
    while (state_queue[temp_id].next != -1)
    {
        printf("%c", state_queue[temp_id].next_dir);
        temp_id = state_queue[temp_id].next;
    }

    printf("
");
}

int main()
{
    int ans = 0;
    char temp_value;

    for (int i = 0; i < 9; ++i)
    {
        cin >> temp_value;
        if (temp_value == 'x')
            map[i] = 9;
        else
            map[i] = temp_value - '0';
    }

    memset(set, 0, sizeof(set));
    ans = BFS();
    if (ans == -1)
        printf("unsolvabel
");
    else if (ans == -2)
        printf("
");
    else
        PrintPath(ans);

    return 0;
}