HDU 1044 Collect More Jewels【BFS+DFS+建立距离图】_collect more jewels java

Collect More Jewels

  
  

   
   3

4 4 2 2
100 200
****
*@A*
*B<*
****

4 4 1 2
100 200
****
*@A*
*B<*
****

12 5 13 2
100 200
************
*B.........*
*.********.*
*@...A....<*
************
  
  

  
  

   
   Case 1:
The best score is 200.

Case 2:
Impossible

Case 3:
The best score is 300.
  
  

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

思路:
先用bfs求出入口，宝物，出口，两两之间的最短距离。
在用dfs搜索所有情况，求出从入口走到出口能获得的最大价值。

熟悉两种搜索的优缺点：
BFS: 对于解决最短或最少问题特别有效，而且寻找深度小，但缺点是内存耗费量大（需要开大量的数组单元用来存储状态）。
DFS：对于解决遍历和求所有问题有效，对于问题搜索深度小的时候处理速度迅速，然而在深度很大的情况下效率不高

#include<stdio.h>
#include<queue>
#include<iostream>
#include<string.h>
using namespace std;
struct node
{
    int x,y,step;
};
int maxx,n,m,many,limit_time,value_sum,val[15];
bool vis2[15],vis[55][55];
int step[4][2]= {1,0,-1,0,0,1,0,-1};
char map[55][55];//原始地图
int newmap[15][15];//新的最短距离标记  但是不是按照这个地图行走
int check(int x,int y)
{
    if(x>=0&&y>=0&&x<n&&y<m)
        return 1;
    return 0;
}
void BFS(int x,int y,int num)//num指的是：  0=@出发点  |  many+1=< 出口点   |  (0,many)  是标记‘A’到‘J’
{
    queue<node>q;
    while(!q.empty())
        q.pop();
    node a,n;
    memset(vis,false,sizeof(vis));
 
    a.x=x;
    a.y=y;
    a.step=0;
    vis[x][y]=true;不加的话 newmap[][]是错误的 newmap中的0会变成2
    q.push(a);
    int nx,ny;
    while(!q.empty())
    {
        a=q.front();
        q.pop();
        for(int i=0; i<4; i++)
        {
            nx=a.x+step[i][0];
            ny=a.y+step[i][1];
            // if(nx>=0&&ny>=0&&nx<=n&&ny<=m)//不能白为什么 code block 不能这样编译 会出错，必须用check才行
            if(check(nx,ny))
            {
                if(map[nx][ny]!='*'&&vis[nx][ny]==false)
                {
                    vis[nx][ny]=true;
                    n.x=nx;
                    n.y=ny;
                    n.step=a.step+1;
                    q.push(n);
                    //找出num点到各个点的最短距离 标记给newmap
                    if(map[nx][ny]=='@') newmap[num][0]=n.step;
                    else if(map[nx][ny]=='<') newmap[num][many+1]=n.step;
                    else if(isalpha(map[nx][ny])) newmap[num][map[nx][ny]-64]=n.step;
                }
            }
        }
    }
}
void DFS(int hang,int value,int step)//hang是指hang这个点 | value 总价值
{
    if(step>limit_time||maxx==value_sum) return ;一个是> 不是>= && 另一个是maxx== 不是value==
    if(hang>many&&value>maxx)//已经找完最后一个宝珠 并且最后一个宝珠也被加到总价值里面了
        maxx=value;    //选出每个深搜后的最大值
    for(int i=0; i<=many+1; i++)是<=不是<
    {
        if(vis2[i]==true||newmap[hang][i]==0) continue;
        vis2[i]=true;
        DFS(i,value+val[i],newmap[hang][i]+step);
        vis2[i]=false;
    }
}
int main(void)
{
    int c,xxx=1;
    scanf("%d",&c);
    while(c--)
    {
        scanf("%d%d%d%d",&m,&n,&limit_time,&many);
        memset(vis2,false,sizeof(vis2));
        memset(newmap,0,sizeof(newmap));
        maxx=-1;
        value_sum=0;之前少输入了这个 一直过不了
        for(int i=1; i<=many; i++) //宝珠的数量
        {
            scanf("%d",&val[i]);
            value_sum+=val[i];
        }
        val[0]=val[many+1]=0;
        for(int i=0; i<n; i++)
        {
            scanf("%s",map[i]);不能吧下一个for放到这里面，因为下一个for里面进行了 搜索
        }
 
 
        //广搜BFS找出各个点之间的最短距离
        for(int i=0; i<n; i++)
        {
            for(int ii=0; ii<m; ii++)
            {
                if(map[i][ii]=='@') BFS(i,ii,0);
                else if(map[i][ii]=='<') BFS(i,ii,many+1);
                else if(isalpha(map[i][ii])) BFS(i,ii,map[i][ii]-64);//@在ascll码里刚好是A前面一个编号64 这里也可以 减-64
            }
        }
        /*
        for(int i=0; i<=many+3; i++)
         {
             for(int ii=0; ii<=many+3; ii++)
             {
                 printf("%3d",newmap[i][ii]);
             }
             printf("\n");
         }
         */
 
         //深搜 找出符合条件最大价值的路径
        vis2[0]=true;
        DFS(0,0,0);
 
 
        //输出部分
        printf("Case %d:\n",xxx++);
        if(maxx==-1)
            printf("Impossible\n");
        else
            printf("The best score is %d.\n",maxx);
        if(c) printf("\n");
    }
    return 0;
}