首页 > 代码库 > HDU-5025 2014广州网络赛 Saving Tang Monk 状压+BFS
HDU-5025 2014广州网络赛 Saving Tang Monk 状压+BFS
给出一个N*N的矩阵,开启牢门需要收集齐m种钥匙,且必须收集了前i-1种钥匙才能收集第i种钥匙,最终收集齐了回到关押唐僧的房间拯救唐僧,经过一个‘S‘的房间时需要额外耗时把蛇打死,蛇最多5条,所以状压一下用优先队列BFS求最小时间即可。
#include <iostream> #include <cstdio> #include <cmath> #include <queue> #include <vector> #include <cstring> #include <algorithm> #define inf 1<<29 using namespace std; const int maxn=111; char str[maxn][maxn]; int n,m; int ans; int map[maxn][maxn]; int dp[maxn][maxn][11];//访问到坐标(x,y)身上有i个钥匙的步数 int dir[4][2]= {0,1,0,-1,1,0,-1,0}; struct node { int x,y; int step; int snake; int k; friend bool operator<(node a,node b) { return a.step>b.step; } }; int go(int x,int y) { if(x>=0&&x<n&&y>=0&&y<n&&str[x][y]!='#') { return 1; } return 0; } void solve(int x,int y) { priority_queue<node> q; node front,now; now.x=x; now.y=y; now.step=0; now.snake=0; now.k=0; q.push(now); while(!q.empty()) { front=q.top(); q.pop(); x=front.x; y=front.y; if(str[x][y]=='T'&&front.k==m) { ans=min(ans,front.step); } for(int i=0;i<4;i++) { int fx=x+dir[i][0]; int fy=y+dir[i][1]; now.x=fx; now.y=fy; now.step=front.step+1; now.snake=front.snake; now.k=front.k; if(go(fx,fy)) { if(str[fx][fy]=='S') { int k=map[fx][fy]; if(((1<<k)&now.snake)==0) { now.step++; now.snake|=(1<<k); } } if(str[fx][fy]-'0'==now.k+1) { now.k+=1; } if(dp[fx][fy][now.k]>now.step&&now.step<ans) { dp[fx][fy][now.k]=now.step; q.push(now); } } } } } int main() { int cnt; while(scanf("%d%d",&n,&m)!=EOF) { if(n==0&&m==0) { break; } cnt=0; for(int i=0;i<n;i++) { scanf("%s",str[i]); } for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(str[i][j]=='S') { map[i][j]=cnt++; } for(int k=0;k<11;k++) { dp[i][j][k]=inf; } } } ans=inf; for(int i=0;i<n;i++) { for(int j=0;j<n;j++) { if(str[i][j]=='K') { solve(i,j); break; } } } if(ans==inf) { printf("impossible\n"); } else { printf("%d\n",ans); } } return 0; }
HDU-5025 2014广州网络赛 Saving Tang Monk 状压+BFS
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。