HDU-1044 Collect More Jewels BFS + DFS

本文主要是介绍HDU-1044 Collect More Jewels BFS + DFS，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*

http://acm.hdu.edu.cn/showproblem.php?pid=1044
一道将BFS和DFS联合起来做的题目。
题意：有一个n*m的castle？然后里面某些点放了些宝藏，每个宝藏都是具有不同的自身价值，现在一个人在入口处，剩下t时间，问怎么样才能在给定的时间下
获得最大的宝藏价值（就是尽量贪婪）
大概的思路：对整个城堡做bfs，bfs求得某个点（其实包含3种，入口。出口。宝藏）到另外一个点（也是那3种）之间的最短路。
然后从入口处开始进行dfs搜索，比较。
算法正确性是确定的，因为：在保证最短路的前提下，我们做的dfs可以搜到任意一种情况，感觉可能导致算法失效的可能性：宝藏A到宝藏C的最短路经历了宝藏B，
那么在DFS的过程中，如果DFS了A->C，那么因为存在比较的过程，最后肯定优先选择A->B->C，这样获得的宝藏更多。这里的dfs是全部可能的dfs.（dfs加了个剪枝）。
/*
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <queue>
using namespace std;
const int maxn = 55;
int n,m,ans,Time,jewels,score,sum;             
char map[maxn][maxn];
bool vis1[maxn][maxn],vis2[maxn];
int val[maxn],dis[maxn][maxn]; //dis[i][j]用来存i到j的最短距离
struct node
{int x,y,step;
};
int xx[] = {0,1,0,-1};
int yy[] = {1,0,-1,0};void BFS( int x,int y,int s )
{node cur,cnt;queue<node>que;cur.x = x;cur.y = y;cur.step = 0;que.push(cur);vis1[x][y] = 1;while( !que.empty() ){cur = que.front(); que.pop();for( int i = 0; i < 4; i ++ ){cnt.x = cur.x + xx[i];cnt.y = cur.y + yy[i];            if( cnt.x >= 1 && cnt.x <= n && cnt.y >= 1 && cnt.y <= m && map[cnt.x][cnt.y] != '*' && !vis1[cnt.x][cnt.y]){vis1[cnt.x][cnt.y] = 1;cnt.step = cur.step + 1;if( isalpha(map[cnt.x][cnt.y]) )dis[s][map[cnt.x][cnt.y]-64] = cnt.step;else if( map[cnt.x][cnt.y] == '@' )dis[s][0] = cnt.step;else if( map[cnt.x][cnt.y] == '<' )dis[s][jewels+1] = cnt.step;que.push(cnt);}}}
}
void dfs( int p,int s,int t )//p表示map[][]中i的性质 ，s表示当前搜索路径可得的宝石价值，t表示当前搜索路径的时间   
{if( t > Time || ans == sum )return;if( p > jewels && s > ans )    ans = s;  //p>jewels说明这一个深搜路径搜到了底（出口）   for( int i = 0; i <= jewels+1; i ++ ){if( dis[p][i] && !vis2[i] ){vis2[i] = 1;dfs( i,s+val[i],t+dis[p][i] );vis2[i] = 0;}}
}
void init()
{ans = -1; sum = 0;    memset( vis2,0,sizeof(vis2) );memset( dis,0,sizeof(dis) );
}
int main()
{int t,cas = 1;//freopen("data.in","r",stdin);scanf("%d",&t);while( t-- ){init();scanf("%d%d%d%d",&m,&n,&Time,&jewels);for( int i = 1; i <= jewels ; i ++ ){scanf("%d",&val[i]);sum += val[i];}val[0] = val[jewels+1] = 0;for( int i = 1; i <= n; i ++ ){scanf("%s",map[i]+1);                    }for( int i = 1; i <= n; i ++ ){for( int j = 1; j <= m; j ++ ){memset( vis1,0,sizeof(vis1) );if( map[i][j] == '@' )    BFS(i,j,0);else if( isalpha(map[i][j]) )   BFS(i,j,map[i][j]-64);  else if( map[i][j]=='<' )  BFS(i,j,jewels+1);  }}vis2[0] = 1;dfs(0,0,0);printf("Case %d:\n",cas++);if( ans>=0 ) printf("The best score is %d.\n",ans);  else printf("Impossible\n");  if(t)puts("");}return 0;
}

这篇关于HDU-1044 Collect More Jewels BFS + DFS的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---