POJ 3523 The Morning after Halloween 题解《挑战程序设计竞赛》

POJ 3523 The Morning after Halloween 

万圣节惊魂夜：万圣节过后，鬼屋里的幽灵们到处乱窜！给定它们的位置和地图，按照如下规则移动：

①每个鬼都不重合

②一回合任意两只鬼不能交换位置

求移动到指定位置所需最少移动次数。

4.5开动脑筋智慧搜索 

A*与IDA* 

一只鬼很好说，最多三只鬼，强加的规则让最优解扑朔迷离。搜索的时候每个状态必须同时包含三只鬼的位置。由于地图很小，坐标系极值在16以内，所以只需4位就能表示x或y。8位表示一个鬼，24位表示三个鬼，一个整型就能放得下整个状态了。

全部状态有256³个，盲目搜索会超时。若不考虑规则的话，分别对3个鬼执行一次BFS就能拿到距离的下界h*(v)。有了下界，就特别适合使用A*了。

#include <iostream>
#include <queue>

using namespace std;
const int dx[] = {0, -1, 1, 0, 0}, dy[] = {0, 0, 0, -1, 1};

/**
 * N个鬼作为整体到目标状态的距离下界
 * @param s 当前状态
 * @param d_min 下界数组
 * @param N 鬼的数量
 * @return
 */
inline int h(const int &s, const unsigned short d_min[3][256], const int &N)
{
    unsigned short l = 0;
    for (int i = 0; i < N; i++)
    {
        l = max(l, d_min[i][(s >> (i << 3)) & 0xff]);
    }
    return l;
}

int move_next(int N, char grid[16][20], int s, int direction[3])
{
    int next = 0;
    for (int i = 0; i < N; i++)
    {
        const int from = (s >> (i << 3)) & 0xff;
        const int to_x = (from >> 4) + dx[direction[i]];
        const int to_y = (from & 0xf) + dy[direction[i]];
        if (grid[to_x][to_y] == '#')
        {
            return -i - 1;  // 撞墙
        }
        const int current = (to_x << 4) | to_y;
        for (int j = 0; j < i; j++)
        {
            const int other = (next >> (j << 3)) & 0xff;
            if (current == other)
            {
                return 0;   // 重合
            }
            if (current == ((s >> (j << 3)) & 0xff) && other == from)
            {
                return 0;   // 交换
            }
        }
        next |= current << (i << 3);
    }
    return next;
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    int W, H, N;
    while (scanf("%d%d%d ", &W, &H, &N), N)
    {
        int init = 0, goal = 0;
        char grid[16][20];
        for (int i = 0; i < H; i++)
        {
            scanf("%[^\n]%*c", grid[i]);
            for (int j = 0; j < W; j++)
            {
                if (islower(grid[i][j]))
                {
                    init |= (i << 4 | j) << ((grid[i][j] - 'a') << 3);
                    grid[i][j] = ' ';
                }
                else if (isupper(grid[i][j]))
                {
                    goal |= (i << 4 | j) << ((grid[i][j] - 'A') << 3);
                    grid[i][j] = ' ';
                }
            }
        }
        const int A = N >= 0 ? 5 : 1;   // 每个鬼能做的动作
        const int B = N >= 1 ? 5 : 1;
        const int C = N >= 2 ? 5 : 1;

        static unsigned short int d_min[3][256]; // d_min[i][j]=n : 第i个鬼的终点离j的距离下界
        for (int i = 0; i < N; i++)
        {
            memset(d_min[i], 0xff, 256 * sizeof(unsigned short int));
            queue<int> q;
            int position = (goal >> (i << 3)) & 0xff;
            q.push(position);
            d_min[i][position] = 0;
            while (!q.empty())
            {
                const int s = q.front();
                const int x = s >> 4;
                const int y = s & 0xf;
                q.pop();
                for (int d = 1; d < 5; d++)
                {
                    const int to_x = x + dx[d];
                    const int to_y = y + dy[d];
                    const int to = (to_x << 4) | to_y;
                    if (grid[to_x][to_y] != '#' && d_min[i][s] + 1 < d_min[i][to])
                    {
                        d_min[i][to] = d_min[i][s] + 1;
                        q.push(to);
                    }
                }
            }
        }

        static unsigned short dist[256 * 256 * 256];
        memset(dist, 0xff, sizeof(dist));
        dist[init] = 0;
        priority_queue<pair<short, int>, vector<pair<short, int>>, greater<pair<short, int> > > q;
        q.push(make_pair(h(init, d_min, N), init));
        while (!q.empty())
        {
            const int cost = q.top().first;
            const int s = q.top().second;
            q.pop();
            if (s == goal)
            {
                printf("%d\n", cost);
                break;
            }
            const int d = cost - h(s, d_min, N);    // 优先队列中存的是cost+h
            if (d > dist[s])
            {
                continue;
            }

            int direction[3];   // 三个鬼的移动方向
            for (direction[0] = 0; direction[0] < A; direction[0]++)
            {
                for (direction[1] = 0; direction[1] < B; direction[1]++)
                {
                    for (direction[2] = 0; direction[2] < C; direction[2]++)
                    {
                        const int next = move_next(N, grid, s, direction);
                        if (next == 0)
                        {
                            continue;       // 违反移动规则，剪枝
                        }
                        else if (next < 0)
                        {
                            if (next == -1)
                            {
                                goto SKIP_A; // 第一只鬼无法移动，剪枝
                            }
                            else if (next == -2)
                            {
                                goto SKIP_B; // 第二个鬼无法移动，剪枝
                            }
                            else
                            {
                                continue;    // 第三只鬼无法移动，剪枝
                            }
                        }
                        if (d + 1 < dist[next])
                        {
                            dist[next] = d + 1;
                            q.push(make_pair(dist[next] + h(next, d_min, N), next));
                        }
                    }
                    SKIP_B:;
                }
                SKIP_A:;
            }
        }
    }
#ifndef ONLINE_JUDGE
    fclose(stdin);
#endif
    return 0;
}

Reference

https://github.com/eagletmt/contests/blob/244c1308ce4ea026626de1f7b08f36069fb45be7/source/2011-10-19-poj-3523.html.liquid.md

 知识共享署名-非商业性使用-相同方式共享：码农场 » POJ 3523 The Morning after Halloween 题解《挑战程序设计竞赛》