首页 > 代码库 > hdu 4771 Stealing Harry Potter's Precious (BFS+状压)

hdu 4771 Stealing Harry Potter's Precious (BFS+状压)

题意:

n*m的迷宫,有一些格能走(“.”),有一些格不能走(“#”)。起始点为“@”。

有K个物体。(K<=4),每个物体都是放在“.”上。

问最少花多少步可以取完所有物体。

 

思路:

BFS+状压,看代码。

 

代码:

struct node{    int x,s;    node(int _x,int _s){        x=_x, s=_s;    }};int n,m,k,sx,sy;char graph[105][105];int px[5],py[5];int dp[105][105][35];int bfs(){    queue<node> q;    mem(dp,-1);    int s=0;    rep(i,1,k) if(px[i]==sx&&py[i]==sy) s=(1<<(i-1));    dp[sx][sy][s]=0;    q.push(node(sx*1000+sy,s));    if(s==((1<<k)-1))        return dp[sx][sy][s];    while(!q.empty()){        node f=q.front();  q.pop();        rep(i,0,3){            int nx=f.x/1000+uu[i], ny=f.x%1000+vv[i];            int s=f.s;            if(nx<0||ny<0||nx>=n||ny>=m) continue;            if(graph[nx][ny]==#) continue;            rep(j,1,k) if(nx==px[j]&&ny==py[j]){                s|=(1<<(j-1));            }            if(dp[nx][ny][s]!=-1) continue;            dp[nx][ny][s]=dp[f.x/1000][f.x%1000][f.s]+1;            q.push(node(nx*1000+ny,s));            if(s==((1<<k)-1))                return dp[nx][ny][s];        }    }    return -1;}int main(){    //freopen("test.in","r", stdin);    while(scanf("%d%d",&n,&m),n||m){        rep(i,0,n-1){            scanf("%s",graph[i]);            rep(j,0,m-1) if(graph[i][j]==@){                sx=i, sy=j;            }        }        scanf("%d",&k);        rep(i,1,k) { scanf("%d%d",&px[i],&py[i]); --px[i], --py[i]; }        printf("%d\n",bfs());    }    //fclose(stdin);}

 

hdu 4771 Stealing Harry Potter's Precious (BFS+状压)