hdu 1044(bfs+状压)
非常经典的一类题型
没有多个出口。这里题目没有说清楚
Collect More Jewels
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4684 Accepted Submission(s): 983
Your goddess The Lady seeks to possess the Amulet, and with it to gain deserved ascendance over the other gods.
You, a newly trained Rambler, have been heralded from birth as the instrument of The Lady. You are destined to recover the Amulet for your deity, or die in the attempt. Your hour of destiny has come. For the sake of us all: Go bravely with The Lady!
If you have ever played the computer game NETHACK, you must be familiar with the quotes above. If you have never heard of it, do not worry. You will learn it (and love it) soon.
In this problem, you, the adventurer, are in a dangerous dungeon. You are informed that the dungeon is going to collapse. You must find the exit stairs within given time. However, you do not want to leave the dungeon empty handed. There are lots of rare jewels in the dungeon. Try collecting some of them before you leave. Some of the jewels are cheaper and some are more expensive. So you will try your best to maximize your collection, more importantly, leave the dungeon in time.
The first line of each test case contains four integers W (1 <= W <= 50), H (1 <= H <= 50), L (1 <= L <= 1,000,000) and M (1 <= M <= 10). The dungeon is a rectangle area W block wide and H block high. L is the time limit, by which you need to reach the exit. You can move to one of the adjacent blocks up, down, left and right in each time unit, as long as the target block is inside the dungeon and is not a wall. Time starts at 1 when the game begins. M is the number of jewels in the dungeon. Jewels will be collected once the adventurer is in that block. This does not cost extra time.
The next line contains M integers，which are the values of the jewels.
The next H lines will contain W characters each. They represent the dungeon map in the following notation:
> [*] marks a wall, into which you can not move;
> [.] marks an empty space, into which you can move;
> [@] marks the initial position of the adventurer;
> [<] marks the exit stairs;
> [A] - [J] marks the jewels.
If the adventurer can make it to the exit stairs in the time limit, print the sentence "The best score is S.", where S is the maximum value of the jewels he can collect along the way; otherwise print the word "Impossible" on a single line.
4 4 2 2
100 200
****
*@A*
*B<*
****
4 4 1 2
100 200
****
*@A*
*B<*
****
12 5 13 2
100 200
************
*B.........*
*.********.*
*@...A....<*
************
The best score is 200.
Case 2:
Impossible
Case 3:
The best score is 300.
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <string>
#include <queue>
#include <stdlib.h>
using namespace std; struct node
{
int x,y,cnt;
}que[]; int n,m,t,tj;
int cost[];
int dis[][];
char g[][];
int sid,tid;
int mlink[][];
int qf,qd;
int up[]={,,-,};
int rl[]={,,,-};
int dp[][][]; void bfs(int sx,int sy)
{
int mark[][];
memset(mark,,sizeof(mark));
qf=qd=;
node finode;
mark[sx][sy]=;
finode.x=sx; finode.y=sy; finode.cnt=;
que[qf++]=finode;
while(qf>qd)
{
node cur=que[qd++];
for(int i=;i<;i++)
{
int tx,ty;
tx=cur.x+up[i];
ty=cur.y+rl[i];
if( (tx>=&&tx<n)&&(ty>=&&ty<m) && g[tx][ty]!='*'&& mark[tx][ty]==)
{
mark[tx][ty]=;
node nwnode;
nwnode.cnt=cur.cnt+;
nwnode.x=tx;nwnode.y=ty;
que[qf++]=nwnode;
if(mlink[tx][ty]!=-)
{
dis[ mlink[tx][ty] ][ mlink[sx][sy] ]=nwnode.cnt;
dis[ mlink[sx][sy] ][ mlink[tx][ty] ]=nwnode.cnt;
}
}
}
}
} int main()
{
int T;
int tt=;
scanf("%d",&T);
int flag=;
while(T--)
{
if(flag) printf("\n");
flag=;
scanf("%d%d%d%d",&m,&n,&t,&tj);
for(int i=;i<tj;i++)
scanf("%d",cost+i);
for(int i=;i<n;i++)
{
scanf("%s",g[i]);
}
memset(dis,-,sizeof(dis));
memset(mlink,-,sizeof(mlink));
int id=;
for(int i=;i<n;i++)
for(int j=;j<m;j++)
{
if(g[i][j]!='.'&&g[i][j]!='*')
{
if(g[i][j]=='@')
mlink[i][j]=;
else if( g[i][j]=='<')
{
id++;
mlink[i][j]=tj+;
}
else mlink[i][j]=g[i][j]-'A'+;
}
}
if(id>=)
{
for(int i=;i<;i++)
printf("%d\n",cost[i]); }
for(int i=;i<n;i++)
for(int j=;j<m;j++)
if(g[i][j]!='.'&&g[i][j]!='<'&&g[i][j]!='*')
{
bfs(i,j);
}
////////////
memset(dp,-,sizeof(dp));
dp[][][]=; for(int i=;i<=tj;i++)
{
for(int j=;j<=tj;j++)
{
for(int k=; k<(<<(tj+)) ;k++)
{
if(dp[i-][j][k]!=- && dp[i-][j][k] < t )
{
for(int p=;p<=tj;p++)
{
if( (k&(<<p)) == &&dis[j][p]!=-)
{
if(dp[i][p][(k|(<<p))]==-) dp[i][p][k|(<<p)] = dp[i-][j][k]+dis[j][p];
else dp[i][p][(k|(<<p))] = min(dp[i][p][(k|(<<p))],dp[i-][j][k]+dis[j][p]);
}
}
}
}
}
}
int ans=-;
for(int i=;i<=tj;i++)
for(int j=;j<=tj;j++)
for(int k=;k<(<<(tj+));k++)
if(dp[i][j][k]!=-&&dis[j][tj+]!=-)
if(dp[i][j][k]+dis[j][tj+]<=t)
{
int tmp=;
for(int p=;p<=tj;p++)
if( ((<<p)&k)!= )
tmp+=cost[p-];
ans=max(ans,tmp);
} printf("Case %d:\n",tt++);
if(ans==-) printf("Impossible\n");
else printf("The best score is %d.\n",ans);
}
return ;
}
最新文章
- web性能优化——代理(nginx)
- str_replace vs preg_replace
- HackerRank "Minimum Penalty Path"
- JavaScript中for..in循环陷阱介绍
- uva 297 quadtrees——yhx
- Nexus4_屏幕截图目录
- 负margin居中
- C#基础——三元表达式
- 5 Logistic回归（一）
- Objective-C中的Category(分类)
- android相关内容
- memcached+tomcat转发forward时 sessionid一直变化的问题
- SQL 统计某一天的数据量时， 使用 dateValue(字段) 与 between 性能差异很明显。
- 漫说996icu黑名单
- docker 基础之私有仓库
- zw量化交易·实盘操作·系列培训班
- python_04 基本数据类型、数字、字符串、列表、元组、字典
- Android Bug：Error:com.android.dex.DexException: Multiple dex files define Landroid/support/design/widget/CoordinatorLayout$LayoutParams;
- 转:OGRE场景管理器介绍
- Linux set unset命令