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[102][102]; int vis[102][102]; int dis[5][5],d_cnt; //d_cnt最后有几个点（包括起点） struct COORD{ int x,y; }coord[5]; int dir[4][2]={{1,0},{0,1},{-1,0},{0,-1}}; int bfs(int &x,int &y){ memset(vis,0,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=0; i<4; ++i){ xx=x1+dir[i][0]; yy=y1+dir[i][1]; if(xx>0&&xx<=n&&yy>0&&yy<=m&&pic[xx][yy]!='#'&&!vis[xx][yy]){ vis[xx][yy]=vis[x1][y1]+1; q.push(xx); q.push(yy); } } } return 0; } int main(){ int i,j,x,y; while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){ for(i=1; i<=n; ++i) for(j=1; j<=m; ++j){ scanf(" %c",&pic[i][j]); if(pic[i][j]=='@') sx=i,sy=j; } scanf("%d",&k); d_cnt=1; coord[0].x=sx; coord[0].y=sy; for(i=0; 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=1; //求距离顺便判断是否可到达 for(i=0; i<d_cnt&&flag; ++i) for(j=i+1; j<d_cnt&&flag; ++j){ flag=bfs(i,j); dis[i][j]=dis[j][i]=flag; } if(!flag) puts("-1"); else{ int p[6],ans=inf; for(i=0; i<d_cnt; ++i) p[i]=i; do{ int sum=0; for(i=0; i<d_cnt-1; ++i) sum+=dis[p[i]][p[i+1]]; ans=min(ans,sum); }while(next_permutation(p,p+d_cnt)&&!p[0]); //全排列枚举 printf("%d ",ans); } } return 0; }
然后还有一个问题希望神牛们能解决：要是K加大到50怎么办？