hdu1044+BFS+DFS+Collect More Jewels

제목:지 도 를 하나 주세요.지도 에 입구 가 하나 있 고 출구 가 하나 있 으 며 보석 이 흩 어 져 있 습 니 다.한 사람 이 입구 부터 정 해진 시간 안에 출구 에 도착 하고 이 과정 에서 가장 큰 보석 을 얻 을 수 있 습 니 다.그 중에서 모든 보석 은 한 번 만 얻 을 수 있 습 니 다.
제목 해법:우선 BFS 를 이용 하여 보석 위치 와 출구 및 입구 위치 에서 다른 보석 이나 출구 또는 입구 까지 의 최 단 거리의 네트워크 를 구축 한 다음 DFS 를 이용 하여 입구 위치 에서 출구 위치 까지 검색 하여 얻 을 수 있 는 최대 보석 가 치 를 구축한다.
DFS 시 두 개의 가지치기(1)에 주의 하여 모든 보석 을 얻 었 을 때(2)이 위치 에 도착 할 때 요구 하 는 시간 보다 많은 시간 을 소모 합 니 다.

#include <iostream>
#include <queue>
#include <cstring>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <utility>
#include <vector>

#define WH 60
#define M 11

using namespace std;

class StatePosistion
{
public:
    int h;
    int w;
    int t;
    StatePosistion(int h, int w, int t):h(h), w(w), t(t){}
    StatePosistion(){}
    ~StatePosistion(){}
};

char tmap[WH][WH];
bool visited[M+1];
int jewels[M], dis[M+1][M+1], maxJewels;
int w, h, L, m, sum;
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

bool isLegel(StatePosistion tm)
{
    return tm.h>=0&&tm.h<h&&tm.w>=0&&tm.w<w&&tmap[tm.h][tm.w]!='*';
}

bool isGoodSite(StatePosistion tm)
{
    return tmap[tm.h][tm.w]=='<' || tmap[tm.h][tm.w]=='@' ||
        (tmap[tm.h][tm.w]>='A' && tmap[tm.h][tm.w]<='J');
}

int getSource(char t)
{
    switch(t){
    case '<':return m+1;
    case '@':return 0;
    default:return t-'A'+1;
    }
}

void bfs(StatePosistion stt)
{
    queue<StatePosistion > Qu;
    bool used[WH][WH];
    int frm=getSource(tmap[stt.h][stt.w]);
    StatePosistion cur;
    memset (used, false, sizeof(used));
    Qu.push(stt);
    used[stt.h][stt.w] = true;
    while (!Qu.empty()){
        cur = Qu.front();
        Qu.pop();
        for (int i = 0; i < 4; ++i){
            StatePosistion temp(cur.h+dir[i][0], cur.w+dir[i][1], cur.t+1);
            if (isLegel(temp) && !used[temp.h][temp.w]){
                used[temp.h][temp.w] = true;
                Qu.push(temp);
                if (isGoodSite(temp)){
                    int to=getSource(tmap[temp.h][temp.w]);
                    dis[frm][to] = temp.t;
                }
            }
        }
    }
}

void getJewels(int curpos, int curtime, int curjewels)
{
    for (int i = 1; i <= m+1; ++i){
        if (!visited[i]){
            visited[i] = true;
            if (i == m+1){
                if (dis[curpos][i] && curtime+dis[curpos][i] <= L){
                    maxJewels = max(maxJewels, curjewels);

                }
            }
            else {
                if (dis[curpos][i] && curtime+dis[curpos][i] <= L){
                    getJewels(i, curtime+dis[curpos][i], curjewels+jewels[i-1]);
                }
            }
            visited[i] = false;
        }
        if (maxJewels == sum)return;
    }
}

void printDis()
{
    for (int i = 0; i <= m+1; ++i){
        for (int j = 0; j <= m+1; ++j){
            printf ("%3d", dis[i][j]);
        }
        printf ("
");
    }
}

void init()
{
    memset (dis, 0, sizeof(dis));
    for (int i = 0; i < h; ++i){
        for (int j = 0; j < w; ++j){
            StatePosistion tm(i, j, 0);
            if (isGoodSite(tm)){
                bfs(tm);
            }
        }
    }
    //printDis();
}

void solve()
{
    init();
    if (dis[0][m+1]==0||dis[0][m+1]>L){
        cout << "Impossible" << endl;
    }
    else {
        memset (visited, false, sizeof(visited));
        visited[0] = true;
        maxJewels = 0;
        getJewels(0, 0, 0);
        cout << "The best score is " << maxJewels << "." << endl;
    }
}

int main()
{
    int t, i;
    cin >> t;
    for (int iCase = 1; iCase <= t; ++iCase){
        cin >> w >> h >> L >> m;
        sum = 0;
        for (i = 0; i < m; ++i){
            cin >> jewels[i];
            sum += jewels[i];
        }
        for (i = 0; i < h; ++i){
            cin >> tmap[i];
        }
        cout << "Case " << iCase << ":" << endl;
        solve();
        if (iCase != t)cout << endl;
    }
    return 0;
}