本文共 5996 字，大约阅读时间需要 19 分钟。

原题链接：

一：原题内容

34 4 2 2100 200*****@A**B<*****4 4 1 2100 200*****@A**B<*****12 5 13 2100 200*************B.........**.********.**@...A....<*************

Case 1:The best score is 200.Case 2:ImpossibleCase 3:The best score is 300.

题目大意：

在一个迷宫中，从起点走到终点，还有几个宝物，问在给定的时间内，到达终点后所能获取的最大价值。

思路:

先用bfs求出入口，宝物，出口，两两之间的最短距离。

在用dfs搜索所有情况，求出从入口走到出口能获得的最大价值。

熟悉两种搜索的优缺点：

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

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

这个程序效率还没有很高，好像有的可以1次bfs就把入口、宝物、出口两两的距离找出来的。继续改进吧。

三：AC代码

#include
   
      #include
    
       #include
     
      using namespace std;int w, h, l, m;//h行，w列，l时间，m宝石数量int val[60];//1到m个宝石的价值char matrix[60][60];bool used[60][60];//bfs访问标记bool visited[60];//dfs访问标记int step[60][60];//走到这步话花费的时间int ans;//结果int sum;//所有宝石的价值和int mov[4][2] = { { -1,0 },{ 1,0 },{ 0,1 },{ 0,-1 } };int dis[60][60];//记录初始位置、各宝石和出口两两间的距离				/* 从(x1,y1)到其他点的距离，s范围是0到m+1,0代表起始位置，m+1表示出口，1到m分别表示第i个宝物 */void BFS(int x1, int y1, int s){	queue
      
        q;	memset(used, 0, sizeof(used));	memset(step, 0, sizeof(step));	int u = x1*w + y1;	q.push(u);	used[x1][y1] = true;	step[x1][y1] = 0;	while (!q.empty())	{		u = q.front();		q.pop();		int x = u / w;		int y = u%w;		for (int i = 0; i < 4; i++)		{			int xx = x + mov[i][0];			int yy = y + mov[i][1];			if (xx < 0 || xx >= h || yy < 0 || yy >= w) continue;			if (used[xx][yy] || matrix[xx][yy] == '*') continue;			used[xx][yy] = true;			step[xx][yy] = step[x][y] + 1;			if (matrix[xx][yy] == '@') dis[s][0] = dis[xx][yy];			else if (matrix[xx][yy] == '<') dis[s][m + 1] = step[xx][yy];			else if (matrix[xx][yy] >= 'A'&&matrix[xx][yy] <= 'J')				dis[s][matrix[xx][yy] - 'A' + 1] = step[xx][yy];			q.push(xx*w + yy);		}	}}/* s表示当前点，value表示获得的价值，time表示花费的时间 */void DFS(int s, int value, int time){	if (time > l) return;	if (ans == sum) return;	if (s > m)	{		if (value > ans)			ans = value;		return;	}	for (int i = 0; i <= m + 1; i++)	{		if (dis[s][i] == 0 || visited[i]) continue;		visited[i] = true;		DFS(i, value + val[i], time + dis[s][i]);		visited[i] = false;	}}int main(){	int T;	scanf("%d", &T);	for (int iCase = 1; iCase <= T; iCase++)	{		memset(dis, 0, sizeof(dis));		scanf("%d%d%d%d", &w, &h, &l, &m);		sum = 0;		ans = -1;		for (int i = 1; i <= m; i++)		{			scanf("%d", &val[i]);			sum += val[i];		}		val[0] = val[m + 1] = 0;//!!!!		for (int i = 0; i < h; i++)			scanf("%s", &matrix[i]);		for (int i = 0; i < h; i++)		{			for (int j = 0; j < w; j++)			{				if (matrix[i][j] == '@') BFS(i, j, 0);				else if (matrix[i][j] == '<') BFS(i, j, m + 1);				else if (matrix[i][j] >= 'A'&&matrix[i][j] <= 'J')					BFS(i, j, matrix[i][j] - 'A' + 1);			}		}		memset(visited, 0, sizeof(visited));		visited[0] = true;		DFS(0, 0, 0);		printf("Case %d:\n", iCase);		if (ans >= 0)printf("The best score is %d.\n", ans);		else printf("Impossible\n");		if (iCase!=T)			printf("\n");	}	return 0;}
      
     
    
   

转载地址：https://blog.csdn.net/LaoJiu_/article/details/51354786 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！