hdu 1044(bfs+dfs+剪枝)
Collect More Jewels
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6739 Accepted Submission(s): 1564
is written in the Book of The Lady: After the Creation, the cruel god
Moloch rebelled against the authority of Marduk the Creator.Moloch stole
from Marduk the most powerful of all the artifacts of the gods, the
Amulet of Yendor, and he hid it in the dark 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.
input will contain multiple test cases. The first line of the input is a
single integer T (1 <= T <= 10) which is the number of test
cases. T test cases follow, each preceded by a single blank line.
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.
should be directed to standard output. Start each case with "Case #:"
on a single line, where # is the case number starting from 1. Two
consecutive cases should be separated by a single blank line. No blank
line should be produced after the last test 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.
#include <iostream>
#include <algorithm>
#include <stdio.h>
#include <string.h>
#include <queue>
using namespace std;
const int INF = ;
int n,m,limit,num;
int dis[][]; ///记录两点之间的距离
int jw[];
struct Node{
int x,y,step,geshu;
}s;
char graph[][];
bool vis[][];
int dir[][]={{,},{-,},{,},{,-}};
bool check(int x,int y){
if(x<||x>n||y<||y>m||vis[x][y]||graph[x][y]=='*') return false;
return true;
}
void bfs(Node s,int k){
queue<Node> q;
vis[s.x][s.y] = true;
s.geshu = ;
q.push(s);
while(!q.empty()){
Node now = q.front();
q.pop();
if(now.geshu==num+) return;
for(int i=;i<;i++){
Node next;
next.x = now.x+dir[i][];
next.y = now.y+dir[i][];
if(!check(next.x,next.y)) continue;
char c = graph[next.x][next.y];
next.step = now.step+;
next.geshu = now.geshu+;
if(c=='.') next.geshu-=;
if(c=='@'){
dis[k][] = next.step;
}
else if(c>='A'&&c<='J') {
dis[k][c-'A'+] = next.step;
}else if(c=='<'){
dis[k][num+] = next.step;
}
vis[next.x][next.y] = true;
q.push(next);
}
}
}
bool vis1[];
int MAX = ,sum;
void dfs(int u,int step,int ans){
if(step>limit || MAX == sum) return ; ///必须要加剪枝
if(u==num+){
MAX = max(MAX,ans);
return;
}
for(int i=;i<=num+;i++){
if(!vis1[i]){
vis1[i] = true;
dfs(i,step+dis[u][i],ans+jw[i]);
vis1[i] = false;
}
}
}
int main(){
int tcase;
scanf("%d",&tcase);
int kk = ;
while(tcase--){
for(int i=;i<;i++){
for(int j=;j<;j++){
dis[i][j] = (i==j)?:INF;
}
}
scanf("%d%d%d%d",&m,&n,&limit,&num);
sum = ;
for(int i=;i<=num;i++){
scanf("%d",&jw[i]);
sum+=jw[i];
}
jw[num+] = jw[] = ;
for(int i=;i<=n;i++){
scanf("%s",graph[i]+);
}
for(int i=;i<=n;i++){
for(int j=;j<=m;j++){
if(graph[i][j]=='@') {
memset(vis,false,sizeof(vis));
s.x = i,s.y = j,s.step=;
bfs(s,);
}
if(graph[i][j]=='<'){
memset(vis,false,sizeof(vis));
s.x = i,s.y = j,s.step=;
bfs(s,num+);
}
if(graph[i][j]>='A'&&graph[i][j]<='J'){
memset(vis,false,sizeof(vis));
s.x = i,s.y = j,s.step=;
bfs(s,graph[i][j]-'A'+);
}
}
}
printf("Case %d:\n",kk++);
if(dis[][num+]>limit){
printf("Impossible\n");
if(tcase) printf("\n");
continue;
}
memset(vis1,false,sizeof(vis1));
MAX = ;
vis1[] = true;
dfs(,,);
printf("The best score is %d.\n",MAX);
if(tcase) printf("\n");
}
}
最新文章
- java多线程系类：JUC线程池：04之线程池原理（三）（转）
- delphi 10 seattle 中 解决IOS 9 限制使用HTTP 服务问题
- C primer plus 练习题 第三章
- Codeforces 424A (思维题)
- Spring学习笔记之初始化和销毁方法的调用次序
- struts2<s:property />标签
- 【深圳，武汉】一加科技（One Plus）招聘，寻找不...
- i++与++i陷阱
- Thinkphp5.0 在自己定义一个公共方法的控制器并且继承了Controller类的时候报错
- BUAA-OO-表达式解析与求导
- Java的慢和稳
- todos+增删改查+js练习
- 基于ubuntu搭建 WordPress 个人博客
- jenkins构建多个项目执行顺序设置
- 了解Katalon的安装及基本使用（for mac）
- POJ 2014.K-th Number 区间第k小 （归并树）
- mac上配置php开发环境
- Android之RAS加密算法测试
- PLSQL_统计信息系列04_统计信息的锁定和删除
- linux连接sybase数据库-isql