POJ 1324(BFS + 状态压缩)

题意：给你一条蛇，要求一以最少的步数走到1,1

思路：

最开始一直没想到应该怎样保存状态，后来发现别人用二进制保存蛇的状态，即每两个节点之间的方向和头节点，二进制最多14位（感觉状态保存都能扯到二进制）。然后就是bfs

问题：

1.最开始完全没想到状态压缩的问题

2.感觉现在做题太急，做题没有足够的思考，思路不清晰便开始写，导致在过程中经常崩盘。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <cstring>

#include <cstdlib>

#include <queue>

#include <algorithm>

typedef long long ll;

using namespace std;

int flag;

const int maxn = 25;

const int ma = (1<<14)+10;

int vis[maxn][maxn];

int sta[maxn][maxn][ma];

struct node

{

//    int snake[15][2];

    int x,y;

    int step;

    int state;

};

node cur;

int t,n,m;

int dir[4][2] = {{-1,0},{0,-1},{1,0},{0,1}};

int matri[20][2];

int get_state()   //蛇的状态

{

    int dir;

    int stat = 0;

    for(int i = t; i > 1; i --)

    {

        int x = matri[i][0]-matri[i-1][0];

        int y = matri[i][1]-matri[i-1][1];

        if(x == -1 && y == 0)

            dir = 0;

        if(x == 0 && y == -1)

            dir = 1;

        if(x == 1 && y == 0)

            dir =2 ;

        if(x == 0 && y == 1)

            dir = 3;

        stat <<= 2;

        stat = stat |dir;

    }

    return stat;

}

bool judge(int x,int y,int x1,int y1,int  state)        //是否吃自己

{

    int s;

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

    {

        s = 3;

        s = state & s;            //取最后两位

        state = state >> 2;

        if(x == x1+dir[s][0] && y == y1+dir[s][1])

            return true;

        x1  = x1 + dir[s][0];

        y1  = y1 + dir[s][1];

    }

    return false ;

}

int get_next(int i,int state)       //去掉高位，输入低位

{

    int x = 0-dir[i][0];

    int y = 0-dir[i][1];

    int dir;

    int k = (1 << ((t - 1) << 1)) - 1;

    if(x == -1 && y == 0)

        dir = 0;

    if(x == 0 && y == -1)

        dir = 1;

    if(x == 1 && y == 0)

        dir =2 ;

    if(x == 0 && y == 1)

        dir = 3;

    state <<= 2;

    state |= dir;

    state = state & k;        //去掉最高位

    return state;

}

void bfs()

{

    queue<node>q;

    cur.step = 0;

    sta[cur.x][cur.y][cur.state] = 1;

    q.push(cur);

    node fo;

    while(!q.empty())

    {

        fo = q.front();

        q.pop();

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

        {

            int x = fo.x+dir[i][0];

            int y = fo.y+dir[i][1];

            int ts = get_next(i,fo.state);

            if(x < 1 || x > n || y <1 || y > m || vis[x][y] || judge(x,y,fo.x,fo.y,fo.state) || sta[x][y][ts])

                continue;

            if(x == 1 && y == 1)

            {

                printf("%d\n",fo.step+1);

                flag = 1;

                return;

            }

            node tmp;

            tmp.x =x ;

            tmp.y = y;

            tmp.step = fo.step + 1;

//            for(int i = t; i >= 1; i--)

//            {

//                tmp.snake[i][0] = tt.snake[i-1][0];

//                tmp.snake[i][1] = tt.snake[i-1][1];

//            }

            tmp.state = ts;

            sta[x][y][tmp.state] = 1;

            q.push(tmp);

        }

    }

}

int main()

{

    int cas= 1;

    while(scanf("%d%d%d",&n,&m,&t) != EOF)

    {

        memset(vis,0,sizeof(vis));

        memset(sta,0,sizeof(sta));

        if(n == 0 && m == 0 && t == 0)

            break;

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

            scanf("%d%d",&matri[i][0],&matri[i][1]);

        int a,b,k;

        scanf("%d",&k);

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

        {

            scanf("%d%d",&a,&b);

            vis[a][b] = 1;

        }

        cur.x = matri[1][0];

        cur.y = matri[1][1];

        cur.state = get_state();

        flag = 0;

        printf("Case %d: ",cas++);

        if(cur.x == 1 && cur.y == 1)

        {

            printf("0\n");

            continue;

        }

        bfs();

        if(!flag)

            printf("-1\n");

    }

}

巴特西

POJ 1324(BFS + 状态压缩)

最新文章

热门文章