UVALive 2520 Holedox Moving（BFS+状态压缩）

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

这个题目在比赛的时候我们是没有做出来的，但是听到他们说进制哈希的时候，感觉真的是挺高端的，于是赛后开始补题，本着我的习惯在看题解之前自己再试着写一遍，我当时存储状态的方法是string + map，我用string将蛇的各个位置都存下来，用map记录这个状态有没有出现过，当时是过了题目中给的样例，我就开始担心STL会不会超时，后来发现想多了，这个方法WA了，至于为什么，我还没明白，或许是状态的处理错误。总之我自己也觉得这个状态有点不靠谱。。于是开始换用题解的方式。发现所谓的进制哈希，其实就是状态压缩，我们的方向一共有4个，数组下标为0,1,2,3.二进制表示00,01,10,11.

发现每一个方向都占用了两位，蛇身的长度（不包含蛇头）最大是7，所以方向状态最多有(1<<14)个，就可以使用vis[x][y][state]表示蛇头的位置和相对位置的状态压缩数值，在这里需要注意几个问题，vis为了节省空间和时间使用bool型的，state存储状态的时候让靠近蛇头的位置存储在低位。这样做的原因就是容易得到蛇移动以后的下一个状态，让它左移两位就可以。

我自己也敲出了代码，但是出现了迷之bug，两个样例都没有过，所以我在别人的代码上加了注释（我的改对了估计就跟他的一模一样了），这是原博客地址，代码及注释如下：

#include <iostream>

#include <cstring>

#include <cstdio>

#include <queue>

using namespace std;

const int MAX_S = ( << ) + ;

const int MAX_N =  + ;

const int INF = ( << );

struct State

{

    int x, y, dis, s;

    State(int x = , int y = , int dis = , int s = ) : x(x), y(y), dis(dis), s(s) {};

};

struct POS

{

    int x,y;

};

POS pos[MAX_N];

int N, M, res, L;

int vis[MAX_N][MAX_N][MAX_S];

int fx[] = {-, , , };

int fy[] = {, , , -};

bool _map[MAX_N][MAX_N];

queue <State> Q;

int get_start()

{

    int dir, dx, dy, s = ;

    for(int i = L - ; i > ; i--)///记录i如何走到i+1，便于回溯

    {

        dx = pos[i].x - pos[i - ].x, dy = pos[i].y - pos[i - ].y;

        if(dx ==  && dy == )

            dir = ;

        else if(dx ==  && dy == -)

            dir = ;

        else if(dx == - && dy == )

            dir = ;

        else if(dx ==  && dy == )

            dir = ;

        s = s << ;

        s = s | dir;

    }

    return s;

}

int get_next_state(int i, int s)

{

    int dir;

    int k = ( << ((L - ) << )) - ;///让（l-1）*2都是1，更高位为0

    int dx = , dy = ;

    dx = dx - fx[i], dy = dy - fy[i];///这里不要忘记将方向取反

    if(dx ==  && dy == )

        dir = ;

    else if(dx ==  && dy == -)

        dir = ;

    else if(dx == - && dy == )

        dir = ;

    else if(dx ==  && dy == )

        dir = ;

    s = s << ;

    s = s | dir;

    s = s & k; /// 去除高位部分

    return s;

}

bool judge_code(int x, int y, int pre_x, int pre_y, int s)///判断会不会咬到自己

{

    int dir;

    for(int i = ; i < L - ; i++)

    {

        dir = ;

        dir = dir & s;

        s = s >> ;

        if(x == pre_x + fx[dir] && y == pre_y + fy[dir])

            return false;

        pre_x = pre_x + fx[dir], pre_y = pre_y + fy[dir];

    }

    return true;

}

void BFS()

{

    State a;

    int dx, dy, s;

    while(!Q.empty())

    {

        a = Q.front();

        Q.pop();

        for(int i = ; i < ; i++)

        {

            dx = a.x + fx[i], dy = a.y + fy[i];

            s = get_next_state(i, a.s);

            if(dx >  && dy >  && dx <= N && dy <= M && !vis[dx][dy][s] && !_map[dx][dy] && judge_code(dx, dy, a.x, a.y, a.s))

            {

                if(dx ==  && dy == )

                {

                    res = a.dis + ;

                    return ;

                }

                vis[dx][dy][s] = ;

                Q.push(State(dx, dy, a.dis + , s));

            }

        }

    }

}

int main()

{

    int s = , _case = ;

    State _start;

    while(scanf("%d%d%d", &N, &M, &L), N + M + L)

    {

        res = INF;

        memset(_map,  , sizeof(_map));

        memset(vis,  , sizeof(vis));

        for(int i = ; i < L; i++)

            scanf("%d%d", &pos[i].x, &pos[i].y);

        int K, u, v;

        scanf("%d", &K);

        for(int i = ; i < K; i++)

        {

            scanf("%d%d", &u, &v);

            _map[u][v] = ;

        }

        if(pos[].x ==  && pos[].y == )

        {

            printf("Case %d: 0\n", ++_case);

            continue;

        }

        s = get_start();

        Q.push(State(pos[].x, pos[].y, , s));

        vis[pos[].x][pos[].y][s] = ;

        BFS();

        if(res == INF)

            printf("Case %d: -1\n", ++_case);

        else

            printf("Case %d: %d\n", ++_case, res);

        while(!Q.empty())

            Q.pop();

    }

    return ;

}