HDU4771(2013 Asia Hangzhou Regional Contest )

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

题目大意：

给你一幅图（N*M）“@”是起点，"#"是墙，“.”是路，然后图上有K个珠宝，

问是否能全部取走珠宝，若能则输出最小步数，否则-1。

思路，可以bfs处理珠宝与珠宝，珠宝与起点的距离同时还可以判断是否可达，

最后因为K<=4,所以枚举路径输出最小ans

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <stack>

#include <queue>

using namespace std;

#define N 102

#define inf 0x3f3f3f3f

int n,m,sx,sy,k;

char pic[][];

int vis[][];

int dis[][],d_cnt;    //d_cnt最后有几个点（包括起点）

struct COORD{

    int x,y;

}coord[];

int dir[][]={{,},{,},{-,},{,-}};

int bfs(int &x,int &y){

    memset(vis,,sizeof(vis));

    queue<int>q;

    q.push(coord[x].x);q.push(coord[x].y);

    int x1,y1,xx,yy,i;

    while(!q.empty()){

        x1=q.front(); q.pop();

        y1=q.front(); q.pop();

        if(x1==coord[y].x&&y1==coord[y].y) return vis[x1][y1];

        for(i=; i<; ++i){

            xx=x1+dir[i][];

            yy=y1+dir[i][];

            if(xx>&&xx<=n&&yy>&&yy<=m&&pic[xx][yy]!='#'&&!vis[xx][yy]){

                vis[xx][yy]=vis[x1][y1]+;

                q.push(xx); q.push(yy);

            }

        }

    }

    return ;

}

int main(){

    int i,j,x,y;

    while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){

        for(i=; i<=n; ++i)

            for(j=; j<=m; ++j){

                scanf(" %c",&pic[i][j]);

                if(pic[i][j]=='@') sx=i,sy=j;

            }

        scanf("%d",&k);

        d_cnt=;

        coord[].x=sx;

        coord[].y=sy;

        for(i=; i<k; ++i){

            scanf("%d%d",&x,&y);

            if(x!=sx||y!=sy){   //判断起点上是否放有珠宝

                pic[x][y]='*';

                coord[d_cnt].x=x;

                coord[d_cnt++].y=y;

            }

        }

        int flag=; //求距离顺便判断是否可到达

        for(i=; i<d_cnt&&flag; ++i)

            for(j=i+; j<d_cnt&&flag; ++j){

                flag=bfs(i,j);

                dis[i][j]=dis[j][i]=flag;

            }

        if(!flag) puts("-1");

        else{

            int p[],ans=inf;

            for(i=; i<d_cnt; ++i) p[i]=i;

            do{

                int sum=;

                for(i=; i<d_cnt-; ++i)

                    sum+=dis[p[i]][p[i+]];

                ans=min(ans,sum);

            }while(next_permutation(p,p+d_cnt)&&!p[]); //全排列枚举

            printf("%d\n",ans);

        }

    }

    return ;

}

然后还有一个问题希望神牛们能解决：要是K加大到50怎么办？