poj 1077 Eight(双向bfs)

题目链接：http://poj.org/problem?id=1077

 

思路分析：题目要求在找出最短的移动路径，使得从给定的状态到达最终状态。

<1>搜索算法选择：由于需要找出最短的移动路径，所以选择bfs搜索

<2>判重方法：

将空格视为数字9，则可以将状态的集合视为1-9的排列组合的集合，根据康托展开，将每一个状态映射到一个正整数中；

在由哈希表进行判重。

<3>状态压缩：在搜索时使用将每个状态转换为一个由1-9组成的9位数字即可进行状态压缩与解压。

<4>双向广度优先搜索的技巧：

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