HDU 1044 Collect More Jewels(BFS+DFS)

HDU 1044 Collect More Jewels(BFS+DFS)

http://acm.hdu.edu.cn/showproblem.php?pid=1044

题意:给你一个R*C的棋盘迷宫,要求你在t时间走出迷宫且输出你能获得的最大珠宝价值和.

分析:

首先我们可以知道图中的有效点只有3种:起点,所有宝珠,终点.其中起点我们编号为0,珠宝编号为1到M,终点编号为M+1.

所以我们先用BFS求出以上任意两个有效点之间的距离,然后DFS从起点开始尝试一一走过每一个还没走到的有效点,只要时间不超过t即可.如果当前点是珠宝点,就把该价值加上,如果当前点是终点,就用当前所获得的价值和s更新ans.

不过代码中还有需要剪枝和注意的细节,需要仔细体会代码.

注意:DFS中不可以定序选取下一点,因为最优解可能必须先走B再走A. 很有可能不存在先A,再B,再C等的最优解.

AC代码:

#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<ctype.h>
using namespace std;
const int maxn=50+10;
int dr[]={-1,1,0,0};
int dc[]={0,0,-1,1};
int R,C,t,M;
int sum,ans;//sum是所有珠宝价值和,ans是解
char map[maxn][maxn];
int abc[maxn][maxn];//abc[i][j]=x表第i个有效点到第j个有效点之间的距离,如果为0表示不存在路径
int dist[maxn][maxn], vis1[maxn][maxn];//BFS时使用
//注意dist[r][c]表示BFS中的id点到(r,c)的最短距离,其中id为0到M+1.而vis1[r][c]类似
int vis2[maxn];                  //DFS时使用
int val[maxn];//宝珠的价值,宝珠从1到M编号

void BFS(int r,int c,int id)
{
    queue<int> Q;
    vis1[r][c]=1;
    dist[r][c]=0;
    Q.push(r*C+c);         //错误1,这里及后面写成了r*R+c了
    while(!Q.empty())
    {
        int z=Q.front(); Q.pop();
        int x=z/C, y=z%C;
        for(int d=0;d<4;d++)
        {
            int xx=x+dr[d], yy=y+dc[d];
            if(xx<0||xx>=R||yy<0||yy>=C||map[xx][yy]=='*') continue;
            if(vis1[xx][yy]) continue;
            vis1[xx][yy]=1;
            dist[xx][yy]= dist[x][y]+1;
            if(map[xx][yy]=='@') abc[id][0] = dist[xx][yy];
            else if(isalpha(map[xx][yy])) abc[id][map[xx][yy]-'A'+1] = dist[xx][yy];
            else if(map[xx][yy]=='<') abc[id][M+1]=dist[xx][yy];
            Q.push(xx*C+yy);
        }
    }
}
void dfs(int p,int s,int time)//当前在第p个有效点,拥有价值s的珠宝,花了time时间
{
    if(time>t || ans==sum) return; //剪枝,朝时了或已经得到最优解了
    if(p==M+1 && s>ans) ans=s;  //到达了终点且总价值s>ans,值得更新
    else for(int i=1;i<=M+1;i++)
    {
        if(vis2[i]==1 || abc[p][i]==0) continue; //第i个有效点已经被走过或不存在从p到i的路径
        vis2[i]=1;
        dfs(i,s+val[i],time+abc[p][i]);
        vis2[i]=0;
    }
}
int main()
{
    int T; scanf("%d",&T);
    for(int kase=1;kase<=T;kase++)
    {
        sum=0;
        memset(abc,0,sizeof(abc));          //错误2,忘记了对abs初始化
        memset(vis2,0,sizeof(vis2));
        scanf("%d%d%d%d",&C,&R,&t,&M);
        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<R;i++) scanf("%s",map[i]);
        for(int i=0;i<R;i++)
        for(int j=0;j<C;j++)
        {
            if(map[i][j]!='@'&&map[i][j]!='<'&&!isalpha(map[i][j])) continue;//非有效点
            memset(vis1,0,sizeof(vis1));
            memset(dist,0,sizeof(dist));
            if(map[i][j]=='@') BFS(i,j,0);
            else if(isalpha(map[i][j])) BFS(i,j,map[i][j]-'A'+1);
            else if(map[i][j]=='<') BFS(i,j,M+1);
        }

        vis2[0]=1;
        ans=-1;
        dfs(0,0,0);//当前在0号点,处于0秒时间且已经获得价值0的珠宝
        if(ans>=0) printf("Case %d:\nThe best score is %d.\n",kase,ans);
        else printf("Case %d:\nImpossible\n",kase);
        if(kase<T) puts("");
    }
    return 0;
}