学步园

         题目比一般的图类的题目稍微绕了点弯子。要根据问题建立解题所需要的图。起始点@和终止点<以及Jewels点共同构成图的点，其之间的最短路径构成了图的边。根据新构成的图，利用深度优先进行解题就可以了。我的解法采用maze存储原问题的图。使用map数组存储最终创建的图，其中记录了临接点和路径长度（map[0].index记录了临接点的个数，其余点的index记录了存储在jewels中Jewel的索引）。建立图的时候，反复进行宽度优先搜索，将临接点存储到map中。然后对map进行深度优先搜索就可以了。

#include<queue>
using namespace std;
#include<stdio.h>
int width,height,jewelsNum;
struct Point{
    int col,row,value;
};
struct Map{
    int index,step;
};
Point jewels[12];
bool mapVisited[12];
Map map[12][12];
char maze[51][51];
const int choice[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
int result,sumValue;
char target;

inline void init()
{
    int assist;
    sumValue=0;
    for(int i=1;i<=jewelsNum;i++)
    {
        scanf("%d",&jewels[i].value);
        sumValue+=jewels[i].value;
    }
    jewelsNum+=1;
    target=jewelsNum+'A';
    for(int i=0;i<height;i++)
    {
        getchar();
        for(int j=0;j<width;j++)
        {
            scanf("%c",&maze[i][j]);
            if(maze[i][j]=='@')
            {
                maze[i][j]='A';
                jewels[0].row=i;
                jewels[0].col=j;
                jewels[0].value=0;
            }
            else if(maze[i][j]=='<')
            {
                maze[i][j]=target;
                jewels[jewelsNum].row=i;
                jewels[jewelsNum].col=j;
                jewels[jewelsNum].value=0;
            }
            else if(maze[i][j]>='A'&&maze[i][j]<='J')
            {
                maze[i][j]+=1;
                assist=maze[i][j]-'A';
                jewels[assist].row=i;
                jewels[assist].col=j;
            }
        }
    }
}
inline bool check(int r,int c)
{
    return r<0||r>=height||c<0||c>=width;
}
inline void buildMap()
{
    bool visited[51][51];
    for(int i=0;i<=jewelsNum;i++)
    {
        memset(visited,0,sizeof(visited));
        map[i][0].index=0;
        visited[jewels[i].row][jewels[i].col]=true;
        queue<Point> que;
        que.push(jewels[i]);
        que.front().value=0;
        while(!que.empty())
        {
            Point newPoint;
            for(int j=0;j<4;j++)
            {
                newPoint.row=que.front().row+choice[j][0];
                newPoint.col=que.front().col+choice[j][1];
                if(check(newPoint.row,newPoint.col)||maze[newPoint.row][newPoint.col]=='*'
                    ||visited[newPoint.row][newPoint.col]) continue;
                visited[newPoint.row][newPoint.col]=true;
                newPoint.value=que.front().value+1;
                que.push(newPoint);
                if(maze[newPoint.row][newPoint.col]!='.')
                {
                    map[i][0].index++;
                    map[i][map[i][0].index].index=maze[newPoint.row][newPoint.col]-'A';
                    map[i][map[i][0].index].step=newPoint.value;
                }
            }
            que.pop();
        }
    }
}
void solve(int depth,int limit,int max)
{
    int row,col;
    for(int i=1;i<=map[depth][0].index;i++)
    { 
        row=jewels[map[depth][i].index].row;
        col=jewels[map[depth][i].index].col;
        if(map[depth][i].step>limit||(map[depth][i].step==limit&&maze[row][col]!=target)||mapVisited[map[depth][i].index]||maze[row][col]=='*') continue;
        if(result==sumValue) return ;
        if(maze[row][col]==target&&max>=result)
            result=max;
        mapVisited[map[depth][i].index]=true;
        solve(map[depth][i].index,limit-map[depth][i].step,max+jewels[map[depth][i].index].value);
        mapVisited[map[depth][i].index]=false;
    }
}
int main()
{
    //freopen("Collect More Jewels.txt","r",stdin);
    int caseNum,limit;
    scanf("%d",&caseNum);
    for(int i=1;i<=caseNum;i++)
    {
        scanf("%d%d%d%d",&width,&height,&limit,&jewelsNum);
        init();
        buildMap();
        memset(mapVisited,0,sizeof(mapVisited));
        result=0;
        mapVisited[0]=true;
        solve(0,limit,0);
        if(result)
            printf("Case %d:\nThe best score is %d.\n",i,result);
        else
            printf("Case %d:\nImpossible\n",i);
        if(i!=caseNum)
            printf("\n");
    }
}