学步园

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1044

此题系BFS和DFS的结合使用，需要理解BFS和DFS的特点。

BFS：对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费较大，需要开辟大量的数组单元来存储状态。

DFS：对于解决遍历和求所有问题有效，对于问题搜索深度小的时候处理迅速，然而在深度很大的情况下效率不高。

问题：在能够走出迷宫的前提下，如何尽可能多（价值之和大）的收集珠宝？

分析：

1、从题目可知，珠宝的数目及每个珠宝的价值我们能够知道，要求“最多”，我们通常会联想到动态规划。但从题目本身看，我们很难看到动态规划的影子。于是我们可以考虑构造动态规划的条件。

2、于是就有了这样的Idea：用BFS，先将“起始点--珠宝”、“珠宝--珠宝”、“珠宝—出口”两两间的最短距离求出来，构造一个新的图，用marix存储，matrix的每个元素即两个点之间的最短距离。

3、然后我们就可以利用动态规划（即这里的DFS）来求满足条件（能够走出迷宫；收集价值量最大的珠宝）的最优路径。

#include<iostream>
#include<queue>
#include<ctype.h>
#include<string.h>
using namespace std;

int T, W, H, M, L;
char dungeon[60][60];
int newMap[60][60];
int value[60];
int totalValue;
int dis[60][60];
int visited1[60][60];
int visited2[60];
int dir[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
int res;

typedef struct{
	int x;
	int y;
}Pos;

queue<Pos> que;

void bfs(int y, int x, int p)
{
	int i;

	while(!que.empty()){
		que.pop();
	}
	Pos cur;
	cur.x = x;
	cur.y = y;
	visited1[y][x] = 1;
	dis[y][x] = 0;
	que.push(cur);
	while(!que.empty()){
		cur = que.front();
		que.pop();
		for(i=0; i<4; i++){
			Pos next;
			next.y = cur.y + dir[i][0];
			next.x = cur.x + dir[i][1];
			if(next.y>=H || next.y<0 || next.x>=W || next.x<0){
				continue;
			}
			if(visited1[next.y][next.x]==0 && dungeon[next.y][next.x]!='*'){
				visited1[next.y][next.x] = 1;
				dis[next.y][next.x] = dis[cur.y][cur.x] + 1;
				if(dungeon[next.y][next.x] == '@'){
					newMap[p][0] = dis[next.y][next.x];
				}
				if(isalpha(dungeon[next.y][next.x])){
					newMap[p][dungeon[next.y][next.x]-64] = dis[next.y][next.x];
				}
				if(dungeon[next.y][next.x] == '<'){
					newMap[p][M+1] = dis[next.y][next.x];
				}
				que.push(next);
			}
		}
	}
}

void dfs(int p, int v, int time)
{
	if(time>L || res==totalValue){
		return ;
	}
	if(p>M && v>res){  //p=M+1说明能够走出去，当v>res时更新res
		res = v;
	}
	for(int i=0; i<=M+1; i++){
		if(newMap[p][i]==0 || visited2[i]){
			continue;
		}
		visited2[i] = 1;
		dfs(i, v+value[i], time+newMap[p][i]);
		visited2[i] = 0;
	}
}
			

int main()
{
	int i, j, k, x;

	scanf("%d", &T);
	x = 1;
	while(T--){
		memset(visited2, 0, sizeof(visited2));
		memset(value, 0, sizeof(value));
		memset(newMap, 0, sizeof(newMap));
		scanf("%d%d%d%d", &W, &H, &L, &M);
		totalValue = 0;  //totalValue是一个剪枝条件，不考虑会超时
		for(j=1; j<=M; j++){
			scanf("%d", &value[j]);
			totalValue += value[j];
		}
		value[0] = value[M+1] = 0;
		for(j=0; j<H; j++){
			scanf("%s", dungeon[j]);
		}
		
		for(i=0; i<H; i++){
			for(j=0; j<W; j++){
				memset(visited1, 0, sizeof(visited1));
				memset(dis, 0, sizeof(dis));
				if(dungeon[i][j]=='@'){
					bfs(i, j, 0);
				}
				if(isalpha(dungeon[i][j])){
					bfs(i, j, dungeon[i][j]-64);
				}
				if(dungeon[i][j] == '<'){
					bfs(i, j, M+1);
				}
			}
		}
		res = -1;
		visited2[0] = 1;
		dfs(0, 0, 0);
		
		printf("Case %d:\n", x++);
		if(res >= 0){
			printf("The best score is %d.\n", res);
		}
		else{
			printf("Impossible\n");
		}
		if(T){
			printf("\n");
		}
	}
}