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): 3548 Accepted Submission(s): 704
Problem Description
It 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
Standard 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.
Output
Results 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.
Sample Input
Sample Output
Source
Asia 2005, Hangzhou (Mainland China), Preliminary
Recommend
JGShining
解題構想:本題は地図圧縮が必要で、直接(BFS+DFS)検索すると、構想が混乱し、タイムアウトします. どのようにテーマを見て、第1の感じは、BFS+DFS、つまりBFSはすべての歩ける場所から終点までの距離を求めて、それからDFSの全図を求めて、断固としてタイムアウトしました.後に地図圧縮を考えて、直接BFS全図を考えて、各宝石、起点、終点の2つの間の距離を求めて、それから配列記憶で新しい地図を形成します.そしてDFSで新しい地図を検索して答えを出す(関連基礎テーマ(リンク):HDU 2614 Beat). 主な問題は2つあります. (一)宝石の位置決めと定価の問題は、この問題が解決できないとBFSができなくなり、新しい地図が形成できなくなる.直接構造体配列で格納(x,y,val)すればよいが,使用する場合は,下付き文字を直接記録することで宝石の地図位置と価値を見つけることができる(始点と終点を処理し,配列の1番目と最後の下付き文字の格納内容にそれぞれ格納する必要がある(Wに対して). (二)DFS検索シーケンスの問題で、この問題が解決できないと答えが間違ってしまう.この問題コードで理解できない場合は、基礎問題リンクを参照してください.ここでは分析しません. 枝切り:終点に届かない枝や遍歴した枝を切るだけでいい(BFSのinmap(next.x,next.y)&&!flag[next.x][next.y]&&map[next.x][next.y]!='*';DFSの:宝石は拾ったことがない(拾わない)、時間は終点まで歩ける(タイムアウトしない),宝石拾い完了フラグおよびmain関数のうち,始点が終点に届かない場合は,そのままImpossibleを出力する.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 3548 Accepted Submission(s): 704
Problem Description
It 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
Standard 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.
Output
Results 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.
Sample Input
3 4 4 2 2 100 200 **** *@A* *B<* **** 4 4 1 2 100 200 **** *@A* *B<* **** 12 5 13 2 100 200 ************ *B.........* *.********.* *@...A....<* ************
Sample Output
Case 1: The best score is 200. Case 2: Impossible Case 3: The best score is 300.
Source
Asia 2005, Hangzhou (Mainland China), Preliminary
Recommend
JGShining
解題構想:本題は地図圧縮が必要で、直接(BFS+DFS)検索すると、構想が混乱し、タイムアウトします. どのようにテーマを見て、第1の感じは、BFS+DFS、つまりBFSはすべての歩ける場所から終点までの距離を求めて、それからDFSの全図を求めて、断固としてタイムアウトしました.後に地図圧縮を考えて、直接BFS全図を考えて、各宝石、起点、終点の2つの間の距離を求めて、それから配列記憶で新しい地図を形成します.そしてDFSで新しい地図を検索して答えを出す(関連基礎テーマ(リンク):HDU 2614 Beat). 主な問題は2つあります. (一)宝石の位置決めと定価の問題は、この問題が解決できないとBFSができなくなり、新しい地図が形成できなくなる.直接構造体配列で格納(x,y,val)すればよいが,使用する場合は,下付き文字を直接記録することで宝石の地図位置と価値を見つけることができる(始点と終点を処理し,配列の1番目と最後の下付き文字の格納内容にそれぞれ格納する必要がある(Wに対して). (二)DFS検索シーケンスの問題で、この問題が解決できないと答えが間違ってしまう.この問題コードで理解できない場合は、基礎問題リンクを参照してください.ここでは分析しません. 枝切り:終点に届かない枝や遍歴した枝を切るだけでいい(BFSのinmap(next.x,next.y)&&!flag[next.x][next.y]&&map[next.x][next.y]!='*';DFSの:宝石は拾ったことがない(拾わない)、時間は終点まで歩ける(タイムアウトしない),宝石拾い完了フラグおよびmain関数のうち,始点が終点に届かない場合は,そのままImpossibleを出力する.
#include<cstdio> #include<cstring> #include<queue> #include<algorithm> using namespace std; int n,m,l,w; char map[50][50]; int flag[50][50]; int time1[14][14]; int flag_jews[14]; int dir[4][2]={1,0,0,1,-1,0,0,-1}; // ， bfs int f,max_valu; struct node // bfs { int x; int y; int t; }; struct node2 // ， dfs { int x; int y; int val; }jews[12]; int inmap(int x,int y)// (x,y) ， bfs { if(x>=0&&x<n&&y>=0&&y<m) return 1; return 0; } int bfs(int x,int y,int x1,int y1) // （x,y） (x1,y1) { int i; node first,next; queue<node> q; if(x==x1&&y==y1) return 0; memset(flag,0,sizeof(flag)); first.x=x; first.y=y; first.t=0; flag[x][y]=1; q.push(first); while(!q.empty()) { first=q.front(); q.pop(); for(i=0;i<4;i++) { next.x=first.x+dir[i][0]; next.y=first.y+dir[i][1]; next.t=first.t+1; if(inmap(next.x,next.y)&&!flag[next.x][next.y]&&map[next.x][next.y]!='*') { if(next.x==x1&&next.y==y1) return next.t; flag[next.x][next.y]=1; q.push(next); } } } return 10000000; } void dfs(int r,int ld,int w1,int val)// r ， ld ， W ， { if(w==0) // return ; for(int i=1;i<w+1;i++) { if(!flag_jews[i]&&time1[i][w+1]<=ld-time1[r][i]) // （ ）， （ ） { val+=jews[i].val; flag_jews[i]=1; max_valu=val>max_valu?val:max_valu; dfs(i,ld-time1[r][i],w1-1,val); val-=jews[i].val; flag_jews[i]=0; } } } int main() { int t; int i,j,k; scanf("%d",&t); for(k=1;k<=t;k++) { f=0; max_valu=0; scanf("%d%d%d%d",&m,&n,&l,&w); jews[0].val=0; jews[w+1].val=0; for(i=1;i<=w;i++) scanf("%d",&jews[i].val); for(i=0;i<n;i++) // { scanf("%s",map[i]); for(j=0;j<m;j++) { if(map[i][j]>='A'&&map[i][j]<='J') // { jews[map[i][j]-'A'+1].x=i; jews[map[i][j]-'A'+1].y=j; } else if(map[i][j]=='@') // { jews[0].x=i; jews[0].y=j; map[i][j]='.'; } else if(map[i][j]=='<') // { jews[w+1].x=i; jews[w+1].y=j; map[i][j]='.'; } } } for(i=0;i<w+2;i++) // ， ， for(j=0;j<w+2;j++) time1[i][j]=time1[j][i]=bfs(jews[i].x,jews[i].y,jews[j].x,jews[j].y); if(k!=1) printf("
"); printf("Case %d:
",k); if(time1[0][w+1]>l) printf("Impossible
"); // ， else { memset(flag_jews,0,sizeof(flag_jews)); flag_jews[0]=1; dfs(0,l,w,0); printf("The best score is %d.
",max_valu); } } return 0; }