这道题可以想到几点：
- 整个行程可以看作一次次的行走，每次行走都是用最短的路程从某一非空点到达另外一非空点；
- 两点间最少的步数是二者x和y坐标差的最大值；
- 返回原点这个过程，肯定是取完最后一个黄金后直接用最少的步数从这儿出发回到原点。
然后就是状压DP了：
dp[u][S]：经过非空点集S后到达u点最少的步数
转移就枚举从哪儿到达u点的。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 #define INF (1<<29) 6 int x[16],y[16],cnt; 7 int d[16][1<<16]; 8 int main(){ 9 int t,n,m; 10 scanf("%d",&t); 11 for(int cse=1; cse<=t; ++cse){ 12 scanf("%d%d",&n,&m); 13 cnt=0; 14 char c; 15 int sx,sy; 16 for(int i=0; i<n; ++i){ 17 for(int j=0; j<m; ++j){ 18 scanf(" %c",&c); 19 if(c=='x') sx=i,sy=j; 20 else if(c=='g') x[cnt]=i,y[cnt]=j,++cnt; 21 } 22 } 23 x[cnt]=sx,y[cnt]=sy,++cnt; 24 25 for(int i=0; i<16; ++i){ 26 for(int j=0; j<(1<<16); ++j) d[i][j]=INF; 27 } 28 d[cnt-1][1<<cnt-1]=0; 29 for(int i=(1<<cnt-1)+1; i<(1<<cnt); ++i){ 30 for(int j=0; j<cnt; ++j){ 31 if(((i>>j)&1)==0 || j==cnt-1) continue; 32 for(int k=0; k<cnt; ++k){ 33 if(((i>>k)&1)==0 || k==j) continue; 34 d[j][i]=min(d[j][i],d[k][i^(1<<j)]+max(abs(x[j]-x[k]),abs(y[j]-y[k]))); 35 } 36 } 37 } 38 int res=INF; 39 for(int i=0; i<cnt; ++i) res=min(res,d[i][(1<<cnt)-1]+max(abs(x[i]-x[cnt-1]),abs(y[i]-y[cnt-1]))); 40 printf("Case %d: %d ",cse,res); 41 } 42 return 0; 43 }