HDU 1044 Collect More Jewels(BFS+DFS)
Collect More Jewels
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6713 Accepted Submission(s): 1558
cavities of Gehennom, the Under World, where he now lurks, and bides his time.
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.
case.
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.
链接:HDU 1044
题目需要转换一下,先用bfs求每一个点到另外其他点的单源最短路dis[now][to],再用dfs进行剪枝搜索……,PE两发……
代码:
#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define MM(x,y) memset(x,y,sizeof(x))
#define LC(x) (x<<1)
#define RC(x) ((x<<1)+1)
#define MID(x,y) ((x+y)>>1)
typedef pair<int,int> pii;
typedef long long LL;
const double PI=acos(-1.0);
const int N=55;
struct info
{
int x;
int y;
int step;
info operator +(info b)
{
b.x+=x;
b.y+=y;
b.step+=step;
return b;
}
};
info direct[4]={{1,0,1},{-1,0,1},{0,1,1},{0,-1,1}};
int n,m,L,M,maxm,ans; char pos[N][N];
int vis[N][N];
int dis[N][N];
int value[15];
int dvis[15];
info S;
void init()
{
MM(pos,0);
MM(dis,INF);
MM(value,0);
maxm=ans=0;
}
bool check(const info &a)
{
return (a.x>=0&&a.x<n&&a.y>=0&&a.y<m&&!vis[a.x][a.y]&&pos[a.x][a.y]!='*'&&a.step<=L);
}
int getnum(const info &s)
{
if(pos[s.x][s.y]=='@')
return 0;
else if(pos[s.x][s.y]=='<')
return M+1;
else if(pos[s.x][s.y]>='A'&&pos[s.x][s.y]<='J')
return pos[s.x][s.y]-'A'+1;
}
void bfs(const info &s)
{
MM(vis,0);
queue<info>Q;
int ins,inr;
ins=getnum(s);
vis[s.x][s.y]=1;
Q.push(s);
while (!Q.empty())
{
info now=Q.front();
Q.pop();
for (int i=0; i<4; ++i)
{
info v=now+direct[i];
if(check(v))
{
vis[v.x][v.y]=1;
if(pos[v.x][v.y]!='.')
{
inr=getnum(v);
dis[ins][inr]=v.step;
}
Q.push(v);
}
}
}
}
void dfs(int now,int t,int v)
{
if(now==M+1)
ans=max(ans,v);
if(ans==maxm)
return ;
for (int i=0; i<=M+1; ++i)
{
if(t+dis[now][i]<=L&&!dvis[i])
{
dvis[i]=1;
dfs(i,t+dis[now][i],v+value[i]);
dvis[i]=0;
}
}
}
int main(void)
{
int tcase,i,j;
scanf("%d",&tcase);
for (int q=1; q<=tcase; ++q)
{
init();
scanf("%d%d%d%d",&m,&n,&L,&M);
for (i=1; i<=M; ++i)
{
scanf("%d",&value[i]);
maxm+=value[i];
}
for (i=0; i<n; ++i)
scanf("%s",pos[i]);
for (i=0; i<n; ++i)
{
for (j=0; j<m; ++j)
{
if(pos[i][j]!='*'&&pos[i][j]!='.')
{
S.x=i;
S.y=j;
bfs(S);
}
}
}
printf("Case %d:\n",q);
if(dis[0][M+1]==INF)
puts("Impossible");
else
{
dvis[0]=1;
dfs(0,0,0);
dvis[0]=0;
printf("The best score is %d.\n",ans);
}
if(q!=tcase)
putchar('\n');
}
return 0;
}
最新文章
- block为什么用copy以及如何解决循环引用
- iOS 学习 - 22 异步解析 JSON,使用 FMDB 存储,TableView 显示
- CSS背景background详解,background-position详解
- UIScrollView在AutoLayout下的滚动问题
- Linux网络基本配置
- BOM (Browser Object Model) 浏览器对象模型
- Nodejs学习笔记(六)--- Node.js + Express 构建网站预备知识
- Word 2010 给公式添加序号
- 简明Vim练级攻略(转载)
- SQL Server缺省约束、列约束和表约束
- NET SignalR 与 LayIM2.0
- sublime 2中Package control安装和使用
- 【管理篇】用户故事STORY
- java jar 后台运行
- go config
- JDBC(11)—数据库连接池
- scrapy中selenium的应用
- oracle kill 锁
- TextView
- python 获取本地语言和编码的代码