POJ 1324 Holedox Moving (状压BFS)

题目解析

状压BFS，除了头结点，其他结点用和前一个结点相对位置来记录

代码

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

#define CLR(a,b) memset(a,b,sizeof(a))

using namespace std;

const int dx[4] = {0,0,1,-1};

const int dy[4] = {1,-1,0,0};

int n,m,k;

int vis[22][22][1<<14];

int stone[22][22];

int ans = -1;

//void show(int z)

//{

//    for(int i = (k-1)*2-1; i>=0; i--){

//        if((1<<i)&z) cout<<"1";

//        else cout<<"0";

//    }

//}

struct Snake

{

    int x,y;

    int zt;

    int t;

}snake;

/*

后一个结点减去前一个结点的值为a b时，记为cd

a  b c d

1  0 0 0

-1 0 0 1

0  1 1 0

0 -1 1 1

*/

bool check_fail(Snake s,int nx,int ny)

{

//    cout<<"check point "<<s.x<<" "<<s.y<<" ZT";

//    show(s.zt);

//    cout<<endl;

    int prex = s.x;

    int prey = s.y;

    int w = (1<<((k-2)*2));

    int t = k - 1;

    while(t--){

        int cx = (s.zt/w)/2;

        int cy = (s.zt/w)%2;

        s.zt%=w;

//        cout<<"cx "<<cx<<" cy "<<cy<<endl;

        int x = prex;

        int y = prey;

        if(cx == 0 && cy == 0) x+=1;

        if(cx == 0 && cy == 1) x-=1;

        if(cx == 1 && cy == 0) y+=1;

        if(cx == 1 && cy == 1) y-=1;

        prex = x;

        prey = y;

        if(x == nx && y == ny) return true;

        w>>=2;

    }

    return false;

}

void bfs(Snake s)

{

    queue<Snake> Q;

    Q.push(s);

    vis[s.x][s.y][s.zt] = 1;

    while(!Q.empty()){

        if(ans != -1){

            break;

        }

        Snake now = Q.front();

        Q.pop();

//        cout<<"Now "<<now.x<<" "<<now.y<<" ZT"<<now.zt<<"  t"<<now.t<<endl;

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

            int x = now.x - dx[i];

            int y = now.y - dy[i];

            int zt = now.zt>>2;

            if(dx[i] == 1 && dy[i] == 0) zt += (0<<((k-2)*2));

            if(dx[i] == -1 && dy[i] == 0) zt += (1<<((k-2)*2));

            if(dx[i] == 0 && dy[i] == 1) zt += (2<<((k-2)*2));

            if(dx[i] == 0 && dy[i] == -1) zt += (3<<((k-2)*2));

            Snake tmp;

            tmp.x = x,tmp.y = y,tmp.zt = zt,tmp.t = now.t+1;

            if(x<1 || x>n || y<1 || y>m || vis[x][y][zt] || stone[x][y]) continue;

            if(check_fail(now,x,y)) continue;

            vis[x][y][zt] = 1;

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

                ans = tmp.t;

                break;

            }

            Q.push(tmp);

        }

    }

}

int main()

{

//    freopen("in.txt","r",stdin);

    int cnt = 0;

    while(scanf("%d%d%d",&n,&m,&k)){

        cnt++;

        if(n == 0 && m == 0 && k == 0) break;

        CLR(vis,0);

        CLR(stone,0);

        snake.zt = 0;

        snake.t = 0;

        ans = -1;

        scanf("%d%d",&snake.x,&snake.y);

        int prex = snake.x;

        int prey = snake.y;

        for(int i = 1; i < k; i++){

            int x,y;

            scanf("%d%d",&x,&y);

            int cx = x - prex;

            int cy = y - prey;

            prex = x;

            prey = y;

            snake.zt<<=2;

            if(cx == 1 && cy == 0) snake.zt += 0;

            if(cx == -1 && cy == 0) snake.zt += 1;

            if(cx == 0 && cy == 1) snake.zt += 2;

            if(cx == 0 && cy == -1) snake.zt += 3;

        }

        int l;

        scanf("%d",&l);

        for(int i = 1; i <= l; i++){

            int x,y;

            scanf("%d%d",&x,&y);

            stone[x][y] = 1;

        }

        bfs(snake);

        if(snake.x == 1 && snake.y == 1) printf("Case %d: %d\n",cnt,0);

        else printf("Case %d: %d\n",cnt,ans);

    }

    return 0;

}