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): 6597    Accepted Submission(s): 1527

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

原題連結： http://acm.hdu.edu.cn/showproblem.php?pid=1044

題意：輸入一個T，代表測試數量，再輸入W，H代表地圖大小，L代表時間，M代表珠寶的數量，‘*’代表牆，‘.’代表路，‘@’代表起點，‘<’代表出口，‘A’-‘J’代表珠寶，下面一行依次表示珠寶的價值，問你在規定的時間最多能拿價值為多少的珠寶出去。

PS：剛開始了解錯了，用了優先隊列+BFS發現WA了，後來才發現可以走重複的路，去拿更多的珠寶，一時沒有了思路，後來參考了邝斌的部落格，才德AC。 思路：先用BFS求出每個珠寶到起點和終點的最短距離，再用DFS搜尋取哪些珠寶的到最大價值。

此題還可以用狀态壓縮。

AC代碼：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
char a[55][55];//地圖
int dis[55][55];//起點，珠寶，出口之間的距離
int step[55][55];//
bool vis[55][55];//BFS标記
bool mark[55];//DFS标記
int val[55];//珠寶價值
int w,h,t,n;
int sum,ans;
int dir[4][2]={1,0,0,1,-1,0,0,-1};
bool OK(int x,int y)
{
    if(x<0||x>=h||y<0||y>=w)
        return false;
    return true;
}
void BFS(int x,int y,int idx)
{
    queue<int>q;
    while(!q.empty())
        q.pop();
    memset(step,0,sizeof(step));
    memset(vis,false,sizeof(vis));
    step[x][y]=0;
    vis[x][y]=true;
    int p=x*w+y;
    q.push(p);
    while(!q.empty())
    {
        p=q.front();
        q.pop();
        int x=p/w;
        int y=p%w;
        for(int i=0;i<4;i++)
        {
            int xx=x+dir[i][0];
            int yy=y+dir[i][1];
            if(OK(xx,yy)&&!vis[xx][yy]&&a[xx][yy]!='*')
            {
                vis[xx][yy]=true;
                step[xx][yy]=step[x][y]+1;
                if(a[xx][yy]=='@')
                    dis[idx][0]=step[xx][yy];
                else if(a[xx][yy]=='<')
                    dis[idx][n+1]=step[xx][yy];
                else if(a[xx][yy]>='A'&&a[xx][yy]<='J')
                    dis[idx][a[xx][yy]-'A'+1]=step[xx][yy];
                q.push(xx*w+yy);
            }
        }
    }
}
//目前收集珠寶價值，目前珠寶價值，消耗時間
void DFS(int s,int value,int time)
{
    //注意下面三條語句的順序
    if(time>t)
        return;
    if(ans==sum)
        return;
    if(s>n)
    {
        if(value>ans)
            ans=value;
        return;
    }
    for(int i=0;i<=n+1;i++)
    {
        if(mark[i]||dis[s][i]==0)
            continue;
        mark[i]=true;
        DFS(i,value+val[i],time+dis[s][i]);
        mark[i]=false;
    }
}

int main()
{
    int T,kase=0;
    cin>>T;
    while(T--)
    {
        cin>>w>>h>>t>>n;
        sum=0;
        for(int i=1; i<=n; i++)
        {
            cin>>val[i];
            sum+=val[i];
        }
        val[0]=val[n+1]=0;
        //把起點和終點當做第一個和最後一個價值為0珠寶
        for(int i=0; i<h; i++)
            cin>>a[i];
        memset(dis,0,sizeof(dis));
        for(int i=0; i<h; i++)
        {
            for(int j=0; j<w; j++)
            {
                if(a[i][j]=='@')
                    BFS(i,j,0);
                else if(a[i][j]=='<')
                    BFS(i,j,n+1);
                else if(a[i][j]>='A'&&a[i][j]<='J')
                    BFS(i,j,a[i][j]-'A'+1);
            }
        }
        memset(mark,false,sizeof(mark));
        mark[0]=true;
        ans=-1;
        DFS(0,0,0);
        cout<<"Case "<<++kase<<":"<<endl;
        if(ans>=0)
            cout<<"The best score is "<<ans<<"."<<endl;
        else
            cout<<"Impossible"<<endl;
        if(T)
            cout<<endl;
    }
    return 0;
}