首页 > 代码库 > HDU 5025 Saving Tang Monk(状压搜索)
HDU 5025 Saving Tang Monk(状压搜索)
钥匙是必须有序,蛇是不要求有序的。所以一个需要状压一个不用
因为时间计算和步数计算不同。所以要遍历整个空间,或者使用优先队列。优先时间短的。
风格就这样了.
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #include <queue> #define inf 0x3f3f3f3f #define maxn 110 using namespace std; int N,M,T; int D[maxn][maxn][10][32]; char G[maxn][maxn]; int dr[]={-1,0,1,0},dc[]={0,1,0,-1}; int sr[5],sc[5],scnt; struct P { int r,c,s,k; }s,e,use,in; int bfs() { queue<struct P> q; q.push(s);int res=inf; while(q.size()){ use=q.front();q.pop(); if(use.k==M && use.r==e.r && use.c==e.c) res=min(res,D[use.r][use.c][use.k][use.s]); for(int i=0;i<4;i++){ int t=1; in=use; in.r=use.r+dr[i]; in.c=use.c+dc[i]; if(D[in.r][in.c][in.k][in.s]!=inf || G[in.r][in.c]=='#' || in.r<1 || in.r>N || in.c<1 || in.c>N) continue; if(G[in.r][in.c]=='S'){ for(int j=0;j<scnt;j++) if(in.r==sr[j] && in.c==sc[j]){ if( (in.s & (1<<j)) ==0) t++,in.s|=1<<j; break; } } else if(G[in.r][in.c]<='9' && G[in.r][in.c]>='1' && G[in.r][in.c]-'0'==in.k+1) in.k++; D[in.r][in.c][in.k][in.s]=D[use.r][use.c][use.k][use.s]+t; q.push(in); } } return res==inf?-1:res; } int main() { while(~scanf("%d%d",&N,&M) && (N+M)){ scnt=0; for(int i=1;i<=N;i++){ getchar(); for(int j=1;j<=N;j++){ scanf("%c",G[i]+j); if(G[i][j]=='K') s.r=i,s.c=j,s.k=0,s.s=0; else if(G[i][j]=='T') e.r=i,e.c=j,e.k=0,e.s=0; else if(G[i][j]=='S') sr[scnt]=i,sc[scnt++]=j; } } memset(D,0x3f,sizeof(D)); D[s.r][s.c][0][0]=0; int ans=bfs(); if(ans==-1) cout<<"impossible"<<endl; else cout<<ans<<endl; } return 0; }
HDU 5025 Saving Tang Monk(状压搜索)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。