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; }