hdu1044

#include <cstdio> #include <cstring> #include <queue> using namespace std; const int maxn=55; int n,m,t,x1,y1,x2,y2; struct node { int x,y; int zb; int step; } ft,et; char ap[maxn][maxn]; int h[11]; bool vis[1100][maxn][maxn]; int dir[4][2]= {{-1,0},{1,0},{0,-1},{0,1}}; int cal(int zb) { int i,j,ans=0; for(i=0,j=1; i<10; i++,j=j*2) if(j&zb) ans+=h[i]; return ans; } void bfs() { memset(vis,false,sizeof(vis)); int i,j,ans=-1; ft.x=x1,ft.y=y1,ft.zb=ft.step=0; vis[0][x1][y1]=true; queue<node>q; q.push(ft); while(!q.empty()) { ft=q.front(); q.pop(); for(i=0; i<4; i++) { et.x=ft.x+dir[i][0]; et.y=ft.y+dir[i][1]; if(et.x<0||et.y<0||et.x>=n||et.y>=m||ap[et.x][et.y]=='*')continue; if(ap[et.x][et.y]!='.')et.zb=(ft.zb|(1<<(ap[et.x][et.y]-'A'))); else et.zb=ft.zb; if(vis[et.zb][et.x][et.y])continue; vis[et.zb][et.x][et.y]=true; et.step=ft.step+1; if(et.x==x2&&et.y==y2) ans=max(ans,cal(et.zb)); if(et.step==t)continue; q.push(et); } } if(ans==-1)printf("Impossible\n"); else printf("The best score is %d.\n",ans); } int main() { int T,tt=0; scanf("%d",&T); while(T--) { int i,j,k; scanf("%d%d%d%d",&m,&n,&t,&k); for(i=0; i<k; i++)scanf("%d",&h[i]); for(i=0; i<n; i++) scanf("%s",ap[i]); for(i=0; i<n; i++) { for(j=0; j<m; j++) { if(ap[i][j]=='@') { x1=i; y1=j; ap[i][j]='.'; } else if(ap[i][j]=='<') { x2=i; y2=j; ap[i][j]='.'; } } } printf("Case %d:\n",++tt); bfs(); if(T!=0)printf("\n"); } return 0; }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 博客园特效简单添加

    @坤的
  • leetcode 23 Merge k Sorted Lists

    @坤的
  • hdu1042

    @坤的
  • Some more technical details about SAP note

    I use this note 2184333 which I am responsible for as an example:

    Jerry Wang
  • 小程序开发总结

    很久很久很久没有更新了,最近几个月因为房子交房,生活上是一片忙碌,工作上的事其实还好,没有分去很多精力,主要是在生活上的事情牵扯了太多了精力,于是乎把每周一更博...

    Originalee
  • MIT 用 AI 实现自动抠图,轻松打造效果惊艳的特效电影

    随着电影越来越关注 CGI,电影制作人必须更加擅长「合成」,即将前景和背景图像融合,比如将演员放在飞机或行星上,或者放在电影《黑豹》里瓦坎达这样的虚构世界中。

    CDA数据分析师
  • MIT提出精细到头发丝的语义分割技术,打造效果惊艳的特效电影

    随着电影越来越关注 CGI,电影制作人必须更加擅长「合成」,即将前景和背景图像融合,比如将演员放在飞机或行星上,或者放在电影《黑豹》里瓦坎达这样的虚构世界中。

    机器之心
  • 微信分享功能大调整:小程序、App、公众号、H5 将全面受限

    知晓君
  • JavaScript : 两个数的精确乘法

    工作中要处理两个数的乘法,网上搜索了没有找到满意的答案,然后根据网上提供的思路自己实现了一个,重点满足容错的要求,就是不会轻易报错。

    LeoXu
  • 【极客周刊】支付宝PK微信?AI程序员面世?等等重大事件等你来看!

    一川水巷

扫码关注云+社区

领取腾讯云代金券