思路:

先用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 105using 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
       
        =0&&y
        
         value[x][y]) return true;    if(t
         
          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
          
           >t;    while(t--)    {        cou++;        cin>>w>>h>>l>>m;        for(i=0;i
           
            >M[i];        getchar();        for(i=0;i
            
             >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
             
              =0) cout<<"The best score is "<
              
               <<"."<
               
                <
               
              
             
            
           
          
         
        
       

在网上搜了一下别人的代码，大致就是先利用bfs构建一个隐氏图，然后再用dfs进行搜索，找到最大价值总和。

#include"iostream"#include"stdio.h"#include"algorithm"#include"cmath"#include"string.h"#include"string"#include"queue"#define mx 105using 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
      
       q;int dir[4][2]={
    {
    0,1},{
    0,-1},{
    1,0},{-1,0}};bool judge(int x,int y)//判断该位置是否可走{    if(x>=0&&x
       
        =0&&y
        
         ='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
         
          >mp[i];        value[0]=0;value[M+1]=0;        for(i=0;i
          
           ='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 "<
           
            <<":"<
            
             0) cout<<"The best score is "<
             
              <<"."<