题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5067
题意：
给你一个n*m的地图，地图上标着对应位置的石子数。你从左上角出发，每次可以向上下左右四个方向移动。你要遍历所有有石子的地方，并返回起点。问你最少的移动步数。
题解：
简化问题：
只保留起点和有石子的点，预处理出保留点两两之间的最短路（曼哈顿距离），将矩阵转化为一个无向图。
原题变为了TSP模板题。
然后套模板就好了。。。
三重for循环，分别枚举state、当前位置i、下一步位置j。
AC Code：
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX_N 55
#define MAX_S (1<<15)
#define INF 10000000 using namespace std; int n,m;
int cnt;
int ans;
int x[MAX_N];
int y[MAX_N];
int dis[MAX_N][MAX_N];
int dp[MAX_S][MAX_N]; void read()
{
cnt=;
int temp;
for(int i=;i<n;i++)
{
for(int j=;j<m;j++)
{
cin>>temp;
if(temp> || (i== && j==))
{
x[cnt]=i;
y[cnt]=j;
cnt++;
}
}
}
} void cal_dis()
{
for(int i=;i<cnt;i++)
{
for(int j=;j<cnt;j++)
{
dis[i][j]=fabs(x[i]-x[j])+fabs(y[i]-y[j]);
}
}
} void solve()
{
cal_dis();
memset(dp,-,sizeof(dp));
dp[][]=;
for(int state=;state<(<<cnt);state++)
{
for(int i=;i<cnt;i++)
{
if(dp[state][i]!=-)
{
for(int j=;j<cnt;j++)
{
if( !((state>>j)&) && (dp[state|(<<j)][j]==- || dp[state|(<<j)][j]>dp[state][i]+dis[i][j]) )
{
dp[state|(<<j)][j]=dp[state][i]+dis[i][j];
}
}
}
}
}
ans=INF;
for(int i=;i<cnt;i++)
{
if(dp[(<<cnt)-][i]!=-) ans=min(ans,dp[(<<cnt)-][i]+dis[i][]);
}
} void print()
{
cout<<ans<<endl;
} int main()
{
while(cin>>n>>m)
{
read();
solve();
print();
}
}