问题描述：
Problem Description 小明误入迷宫，塞翁失马焉知非福，原来在迷宫中还藏着一些财宝，小明想获得所有的财宝并离开迷宫。因为小明还是学生，还有家庭作业要做，所以他想尽快获得所有财宝并离开迷宫。
Input 有多组测试数据。
每组数据第一行给出两个正整数n,m(0 < n,m<=100)。代表迷宫的长和宽。
接着n行，每行m个整数。正数代表财宝(财宝的个数不超过10)；负数代表墙，无法通过；0代表通道。
每次移动到相邻的格子，所花费的时间是1秒。小明只能按上、下、左、右四个方向移动。
小明的初始位置是（1,1）。迷宫的出口也在（1,1）。
Output 输出获得所有财宝并逃出迷宫所花费的最小时间，如果无法完成目标则输出-1。
Sample Input 3 3 0 0 0 0 100 0 0 0 0 2 2 1 1 1 1 Sample Output 4 4
思路分析：
我发现这个题和以前做过TSP问题有点类似。 TSP是给出N个点，每个点都是连通的。每条路都有一个权值。然后你从起点出发，走过所有的点再回到起点。 当时是先用folyd算法，找到每个点之间的最短路。然后，用状压dp求出最小花费。 这道题，是让走过所有有财宝的点，并回到起点。所用的最小花费。 那么我们可以仿照TSP的套路。先用bfs求出，具有宝物的点之间的最短路。 再通过状压dp求出最短路。 这样思路就很清晰了。 详情见代码。
ac代码：
#include<bits/stdc++.h> using namespace std; struct Node { int x,y,step; }; int Map[110][110],vis[110][110],dis[110][110],X[110],Y[110]; int n,m,tot; int d[][2]= {0,1,0,-1,-1,0,1,0}; void bfs(int x,int y,int v) { memset(vis,0,sizeof(vis)); queue<Node> Q; Q.push((Node){x,y,0}); vis[x][y]=1; int cnt=0; while(!Q.empty()) { Node tp=Q.front(); if(cnt==tot) break; Q.pop(); for(int p=0; p<4; p++) { int tx=tp.x+d[p][0],ty=tp.y+d[p][1]; if(tx<0 || ty<0 || tx>=n || ty>=m) continue; if(vis[tx][ty] || Map[tx][ty]<0) continue; if(Map[tx][ty]>0) dis[v][Map[tx][ty]]=tp.step+1,cnt++; Q.push((Node) { tx,ty,tp.step+1 }); vis[tx][ty]=1; } } } int dp[1<<11][13]; //dp[i][j].代表在i状态下，最后一个点为j所需要的最小步数 int main() { while(cin>>n) { cin>>m; tot=1; for(int i=0; i<n; i++) for(int j=0; j<m; j++) { scanf("%d",&Map[i][j]); if(i==0 && j==0) continue; if(Map[i][j]>0) X[++tot]=i,Y[tot]=j,Map[i][j]=tot; } if(Map[0][0]==-1) { cout<<-1<<endl; continue; } X[1]=0,Y[1]=0,Map[0][0]=1; memset(dis,-1,sizeof(dis)); for(int i=1; i<=tot; i++) bfs(X[i],Y[i],i); memset(dp,-1,sizeof(dp));//初始化 dp[1][0]=0;//初始化 for(int i=0; i<(1<<tot); i++) //枚举所有状态。 for(int j=0; j<tot; j++) //枚举在该状态下，最后一个点。 { if(dp[i][j]==-1 || (i&(1<<j))==0) continue; //如果该状态没有经过j点跳过。 for(int k=0; k<tot; k++) //在该状态的基础上再加入一个点。 { if(k==j || dis[j+1][k+1]==-1) continue; int s=i|(1<<k); if(dp[s][k]==-1) dp[s][k]=dp[i][j]+dis[j+1][k+1]; else dp[s][k]=min(dp[s][k],dp[i][j]+dis[j+1][k+1]); } } cout<<dp[(1<<tot)-1][0]<<endl; } return 0; }