原题大意

在能走出迷宫的情况下,收集最大价值的珠宝,’*’是墻,’.’表示可以走的空地,’@’表示起点,’<’表示终点,’A-J’用来表示各种价值的珠宝.

算法分析

这题百度了下,我能用的方法就是bfs加dfs,先用bfs算出出口,入口,珠宝之间的两两最短距离,然后再用dfs遍历每条从起点到终点的路径.

注意事项

这题我一开始交的时候总是超时,后来百度了下,在dfs里加了段代码,作用是如果收集的珠宝已达到所有珠宝价值之和,递归就结束.(这是我第一次超时,下次再出现时要考虑清楚哪里可以缩短时间)

程序代码

#include <iostream>
#include <queue>
#include <memory.h>
using namespace std;
int W,H,L,M;
int dx[]={1,0,-1,0};
int dy[]={0,1,0,-1};
char g[50][50];
int len[12][12];//宝物,出入口的两两距离 
int l[50][50];//记录距离 
bool used[12];//dfs剪枝 
bool visit[50][50]; //bfs剪枝
int val[12];//宝物价值 
int a[13];//宝物,出入口的坐标 
int maxval=0;
queue<int> q;
void bfs(int x1,int y1,int n)
{
    while(!q.empty()) q.pop();
    q.push(a[n]);
    visit[x1][y1]=1;
    while(!q.empty())
    {

        int t=q.front();
        q.pop();
        for(int i=0;i<4;i++)
        {
            int xx,yy;
            xx=x1+dx[i];
            yy=y1+dy[i];
            if(xx<0||xx>=H||yy<0||yy>=W) continue;
            if(g[xx][yy]=='*'||visit[xx][yy]) continue;

            visit[xx][yy]=true;
            l[xx][yy]=l[x1][y1]+1;
            int mm;
            if(g[xx][yy]=='.')
            {
                q.push(xx*W+yy);
                continue;
            }
            if(g[xx][yy]=='@') mm=0;
            if(g[xx][yy]=='<') mm=M+1;
            else mm=g[xx][yy]-'A'+1;
            len[n][mm]=l[xx][yy];
            q.push(xx*W+yy);
        } 
    }    
}
void dfs(int s,int time,int value)
{
    if(time>L) return ;
    if(s==M+1)
    {
        if(value>maxval)
            maxval=value;
        return ;
    }
    for(int i=1;i<=M+1;i++)        //与for(int i=1;i<=M+1&&!used[i];i++)
    {                            // 不同 
        if(used[i]) continue;    
        used[i]=1;
        dfs(i,time+len[s][i],value+val[i]);
        used[i]=0;
    }

}
int main()
{
    int r;
    scanf("%d",&r);
    for(int Case=1;Case<=r;Case++)
    {
        printf("\n");
        scanf("%d%d%d%d",&W,&H,&L,&M);
        for(int i=1;i<=M;i++)
            scanf("%d",&val[i]);
        val[0]=val[M+1]=0;
        for(int i=0;i<H;i++)
            scanf("%s",g[i]); 
        for(int i=0;i<H;i++)
            for(int j=0;j<W;j++)
                {
                    if(g[i][j]=='@') a[0]=i*W+j;
                    if(g[i][j]=='<')
                    {
                         a[M+1]=i*W+j;
                    }
                    if(g[i][j]>='A'&&g[i][j]<='A'+10)
                        a[g[i][j]-'A'+1]=i*W+j;
                }
        for(int i=0;i<=M+1;i++)
        {
            memset(visit,0,sizeof(visit));
            memset(l,0,sizeof(l));
            bfs(a[i]/W,a[i]%W,i);
        }
        memset(used,0,sizeof(used));
        dfs(0,0,0); 
        if(maxval==0)
            printf("Case %d:\nImpossible\n",Case);
        else
            printf("Case %d:\nThe best score is %d\n",Case,maxval);
        maxval=0;
    }
    return 0;
}