思路:
先用bfs求出入口，宝物，出口，两两之间的最短距离。
在用dfs搜索所有情况，求出从入口走到出口能获得的最大价值。
我们要解决几个问题：1、求入口到第一个取宝物的地方的最短距离
2、求第i个取宝物的地方到第i+1个取宝物的地方的最短距离
3、求第n个取宝物的地方到出口的最短距离
4、保证以上3点能在时间L内实现的情况下，取得的宝石价值最大
熟悉两种搜索的优缺点：
BFS: 对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组单元用来存储状态）。
DFS：对于解决遍历求和问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高
dfs剪枝：
1.step>time直接return。
2.ans==sum时就不用再搜了 因为已经到最大了。
3.如果搜到一个点，这个点以前已经搜过，而且现在到达这个点时珠宝价值比以前少而且走的步数却比以前多，就不用搜这个点了。
真是被自己傻到了 。。。花了一个小时写了一个代码如下，感觉自己真是太弱智了，居然放这么大的错误，忽略了两件宝物可以在一条路径上，所以 以后编程还是要考虑周全在下手 ，尤其是比赛的时候，一旦有大的漏洞，就会被 坑哭了。。。
错误代码：
#include"iostream" #include"stdio.h" #include"algorithm" #include"cmath" #include"string" #include"string.h" #include"queue" #include"stack" #include"vector" #define mx 105 using namespace std; int g[mx][mx]; int value[mx][mx];//存放每个点的价值 int time[mx][mx];//存放每个点的时间 int M[mx];//存放宝物的价值 int h,w,m,l,sx,sy,ex,ey,maxvalue; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; struct node { int x,y; int times; int values; }; bool judge1(int x,int y)//判断能不能走 { if(x>=0&&x<h&&y>=0&&y<w&&g[x][y]!=-1) return true; return false; } bool judge2(int x,int y,int v,int t)//判断应不应该走 { if(v>value[x][y]) return true; if(t<time[x][y]) return true; return false; } void bfs() { queue<node>q; node cur,next; int i; cur.x=sx;cur.y=sy;cur.times=0;cur.values=0; q.push(cur); while(!q.empty()) { cur=q.front(); q.pop(); if(cur.x==ex&&cur.y==ey&&cur.times<=l) { if(maxvalue<cur.values) maxvalue=cur.values; } for(i=0;i<4;i++) { next.x=cur.x+dir[i][0]; next.y=cur.y+dir[i][1]; if(judge1(next.x,next.y)) { next.times=cur.times+1; next.values=cur.values+g[next.x][next.y]; if(judge2(next.x,next.y,next.values,next.times)) { q.push(next); time[next.x][next.y]=next.times; value[next.x][next.y]=next.values; g[next.x][next.y]=0; } } } } } int main() { int i,j,t,cou=0;; char ch; cin>>t; while(t--) { cou++; cin>>w>>h>>l>>m; for(i=0;i<m;i++) cin>>M[i]; getchar(); for(i=0;i<h;i++) { for(j=0;j<w;j++) { cin>>ch; switch(ch) { case '*':g[i][j]=-1;break; case '.':g[i][j]=0;break; case '@':g[i][j]=0;sx=i;sy=j;break; case '<':g[i][j]=0;ex=i;ey=j;break; default: g[i][j]=M[ch-'0'-65];break; } } } memset(value,0,sizeof(value)); for(i=0;i<h;i++) for(j=0;j<w;j++) time[i][j]=1000001; maxvalue=-1; bfs(); cout<<"Case "<<cou<<":"<<endl; if(maxvalue>=0) cout<<"The best score is "<<maxvalue<<"."<<endl<<endl; else cout<<"Impossible"<<endl<<endl; } return 0; }
在网上搜了一下别人的代码，大致就是先利用bfs构建一个隐氏图，然后再用dfs进行搜索，找到最大价值总和。
#include"iostream" #include"stdio.h" #include"algorithm" #include"cmath" #include"string.h" #include"string" #include"queue" #define mx 105 using namespace std; char mp[mx][mx]; bool used[mx][mx];//标记bfs走过的路径 bool vis[mx];//标记 dfs走过的路径 int value[mx];//记录宝物的价值 int H,W,L,M,ans,sum; int step[mx][mx];//记录每个位置的最小步骤 int dis[mx][mx];//记录出口、入口、宝物两两之间的最短距离 queue<int>q; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; bool judge(int x,int y)//判断该位置是否可走 { if(x>=0&&x<H&&y>=0&&y<W&&mp[x][y]!='*') return true; return false; } void bfs(int x1,int y1,int s) { while(!q.empty()) q.pop(); int dx,dy,i,u,x,y; memset(used,false,sizeof(used)); memset(step,0,sizeof(step)); u=x1*W+y1; q.push(u); used[x1][y1]=true; step[x1][y1]=0; while(!q.empty()) { u=q.front(); q.pop(); x=u/W; y=u%W; for(i=0;i<4;i++) { dx=x+dir[i][0]; dy=y+dir[i][1]; if(judge(dx,dy)) { if(!used[dx][dy]) { used[dx][dy]=true; step[dx][dy]=step[x][y]+1; if(mp[dx][dy]=='@') dis[s][0]=step[dx][dy]; else if(mp[dx][dy]=='<') dis[s][M+1]=step[dx][dy]; else if(mp[dx][dy]>='A'&&mp[dx][dy]<='J') dis[s][mp[dx][dy]-'A'+1]=step[dx][dy]; q.push(dx*W+dy); } } } } } void dfs(int s,int val,int time) { int i; if(time>L) return; if(ans==sum) return; if(s>M) { if(val>ans)ans=val; return; } for(i=0;i<=M+1;i++) { if(dis[s][i]==0||vis[i]) continue; vis[i]=true; dfs(i,value[i]+val,time+dis[s][i]); vis[i]=false; } } int main() { int i,j,t,icase=0; cin>>t; while(t--) { sum=0;ans=-1; memset(dis,0,sizeof(dis));//记得初始化dis icase++; cin>>W>>H>>L>>M; for(i=1;i<=M;i++) {cin>>value[i];sum+=value[i];} for(i=0;i<H;i++) cin>>mp[i]; value[0]=0;value[M+1]=0; for(i=0;i<H;i++) { for(j=0;j<W;j++) { if(mp[i][j]=='@') bfs(i,j,0); else if(mp[i][j]=='<')bfs(i,j,M+1); else if(mp[i][j]>='A'&&mp[i][j]<='J') bfs(i,j,mp[i][j]-'A'+1); } } memset(vis,false,sizeof(vis)); vis[0]=true; dfs(0,0,0); cout<<"Case "<<icase<<":"<<endl; if(ans>0) cout<<"The best score is "<<ans<<"."<<endl; else cout<<"Impossible"<<endl; if(t) cout<<endl; } }