一开始看宝藏只有10个，100*100的矩阵，果断写了状压BFS，然后果断超时。。正解:先不考虑财宝，先做BFS算出，每个财宝之间的最短路（包括起点），，然后状压最短路处理即可。注意三中情况：起点为负数，不存在财宝，存在一个财宝且财宝在原点。#include "stdio.h"#include "string.h"#include "algorithm"#include "queue"using namespace std;const int inf=0x3f3f3f3f;struct Mark{int x,y;}mark[15];struct node{int x,y,t;};int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };int b[15];int str[110][110];int dis[15][15];int n,m,cnt;int used[110][110];int dp[5010][15];int Min(int a,int b){if (a<b) return a;else return b;}void bfs(int w){queue<node>q;node cur,next;int i;memset(used,0,sizeof(used));cur.x=mark[w].x;cur.y=mark[w].y;cur.t=0;q.push(cur);used[mark[w].x][mark[w].y]=1;while (!q.empty()){cur=q.front();q.pop();for (i=0;i<4;i++){next.x=cur.x+dir[i][0];next.y=cur.y+dir[i][1];if (next.x<0 || next.y<0 || next.x>=n || next.y>=m) continue;if (str[next.x][next.y]<0) continue;if (used[next.x][next.y]==0){used[next.x][next.y]=1;next.t=cur.t+1;if (str[next.x][next.y]>0){dis[w][str[next.x][next.y]]=Min(dis[w][str[next.x][next.y]],next.t);dis[str[next.x][next.y]][w]=dis[w][str[next.x][next.y]];}q.push(next);}}}}int main(){int i,j,ans,flag,aim,l;b[0]=1;for (i=1;i<=12;i++)b[i]=b[i-1]*2;while (scanf("%d%d",&n,&m)!=EOF){cnt=0;for (i=0;i<n;i++)for (j=0;j<m;j++){scanf("%d",&str[i][j]);if (str[i][j]>0 && i+j!=0){mark[++cnt].x=i;mark[cnt].y=j;str[i][j]=cnt;}}if (cnt==0){printf("0\n");continue;}if (cnt==1 && str[0][0]>0){printf("0\n");continue;}if (str[0][0]<0){printf("-1\n");continue;}mark[0].x=0;mark[0].y=0;memset(dis,inf,sizeof(dis));for (i=0;i<=cnt;i++)bfs(i);flag=1;for (i=1;i<=cnt;i++)if (dis[0][i]==inf){printf("-1\n");flag=0;}if (flag==0) continue;memset(dp,inf,sizeof(dp));dp[1][0]=0;aim=b[cnt+1]-1;for (l=0;l<=aim;l++)for (i=0;i<=cnt;i++)for (j=0;j<=cnt;j++)if (i!=j){if ((b[i]&l)==0) continue;if ((b[j]&l)!=0) continue;if (dp[l][i]==inf) continue;dp[l|b[j]][j]=Min(dp[l|b[j]][j],dp[l][i]+dis[i][j]);}ans=inf;for (i=1;i<=cnt;i++)ans=Min(ans,dp[aim][i]+dis[i][0]);printf("%d\n",ans);}return 0;}
只能昏昏沉沉地沿着青草和泥土的气息前进。
