标准的TSP问题
m*n矩阵，有不超过10个需要走到的点，，给出起点，问走最少的步子把所有点走完
BFS出每个必须走到的点的最短距离
然后状压DP即可
#include "stdio.h"#include "string.h"#include "queue"using namespace std;const int dir[4][2]={ {1,0},{-1,0},{0,1},{0,-1} };int inf=0x7fffffff;int aim,cnt,n,m,s_x,s_y;int b[20];int used[25][25];int dp[5010][25];char str[25][25];int dis[25][25];struct node{int x,y,step;};struct Point{int x,y;}point[25];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;cur.x=point[w].x;cur.y=point[w].y;memset(used,-1,sizeof(used));used[cur.x][cur.y]=0;q.push(cur);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.x>=n || next.y<0 || next.y>=m) continue;if (str[next.x][next.y]=='x') continue;if (used[next.x][next.y]==-1){used[next.x][next.y]=used[cur.x][cur.y]+1;q.push(next);if (str[next.x][next.y]>='a' && str[next.x][next.y]<'o')dis[w][str[next.x][next.y]-'a'+1]=dis[str[next.x][next.y]-'a'+1][w]=used[next.x][next.y];}}}}int main(){int i,j,ii,ans,k;b[0]=0;b[1]=1;for (i=2;i<=15;i++)b[i]=b[i-1]*2;while (scanf("%d%d",&m,&n)!=EOF){if (n+m==0) break;for (i=0;i<n;i++)scanf("%s",str[i]);cnt=0;for (i=0;i<n;i++)for (j=0;j<m;j++)if (str[i][j]=='o'){point[0].x=i;point[0].y=j;}elseif (str[i][j]=='*'){cnt++;str[i][j]='a'+cnt-1;point[cnt].x=i;point[cnt].y=j;}if (cnt==0){printf("0\n");continue;}memset(dis,-1,sizeof(dis));for (i=0;i<cnt;i++)bfs(i);memset(dp,-1,sizeof(dp));dp[0][0]=0;aim=b[cnt+1]-1;for (ii=1;ii<=10;ii++)for (i=0;i<=aim;i++)for (j=0;j<=cnt;j++)if ((b[j]&i)!=0 || j==0)for (k=1;k<=cnt;k++)if ((b[k]&i)==0 && k!=j){if ((dp[i|b[k]][k]==-1 || dp[i|b[k]][k]>dp[i][j]+dis[j][k]) && dp[i][j]!=-1 && dis[j][k]!=-1)dp[i|b[k]][k]=dp[i][j]+dis[j][k];}ans=inf;for (i=1;i<=cnt;i++)if (dp[aim][i]!=-1)ans=Min(ans,dp[aim][i]);if (ans==inf) printf("-1\n");else printf("%d\n",ans); }return 0;}
人生至少要有两次冲动，一为奋不顾身的爱情，一为说走就走的旅行。
