首页 > 代码库 > 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+状压)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。