FZU2186 – 小明的迷宫(TSP+最短路)

题目链接：FZU2186

【分析】因为宝物最多有10个，所以可以状压TSP来求，其实和HDU4568几乎一样，求出所有宝物之间的最短路，然后就是标准TSP问题啦。

【AC CODE】46ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <map>
//#include <unordered_map>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 100+10;
const int f[4][2]={{-1,0},{1,0},{0,-1},{0,1}};
struct NODE{
	int x,y;
	NODE(int a = 0, int b = 0)
	{
		x = a;
		y = b;
	}
}p[15];
int h,w,mp[MAXN][MAXN], cnt, dis[15][15], d[MAXN][MAXN];
bool vis[MAXN][MAXN];

int bfs(int st, int ed)
{
	queue<NODE> q;
	clc(vis,0);
	q.push(p[st]);
	d[p[st].x][p[st].y] = 0;
	vis[p[st].x][p[st].y] = 1;
	while(!q.empty())
	{
		NODE now = q.front();q.pop();
		if(now.x == p[ed].x && now.y == p[ed].y) return d[now.x][now.y];
		rep(i,0,4)
		{
			int ni = now.x+f[i][0], nj = now.y+f[i][1];
			if(0 <= ni && h > ni && 0 <= nj && w > nj && !vis[ni][nj] && mp[ni][nj] >= 0)
			{
				q.push(NODE(ni,nj));
				d[ni][nj] = d[now.x][now.y]+1;
				vis[ni][nj] = true;
			}
		}
	}
	return INF;
}
int dp[1<<13][15];
int main()
{
#ifdef SHY
	freopen("e:\\1.txt", "r", stdin);
#endif
	while(~scanf("%d %d%*c", &h, &w))
	{
		cnt = 1;
		rep(i,0,h)
		{
			rep(j,0,w)
			{
				scanf("%d%*c", &mp[i][j]);
				if(mp[i][j] > 0)
					p[cnt++] = NODE(i,j);
			}
		}
		if(-1 == mp[0][0])
		{
			puts("-1");
			continue;
		}
		p[cnt++] = NODE(0,0);
		clc(dis,0);
		rep(i,0,cnt)
		{
			rep(j,i+1,cnt)
			{
				dis[i][j] = dis[j][i] = bfs(i,j);
			}
		}
		cnt--;
		int ALL = (1<<cnt)-1;
		clc(dp,0x3f);
		clc(dp[0],0);
		rep(i,0,cnt) dp[1<<i][i] = dis[0][i];
		repe(i,1,ALL)
		{
			rep(j,0,cnt)//当前在点j
			{
				if(0 == (1<<j)&i) continue;
				rep(k,0,cnt)//来自上一个点k
				{
					if((1<<k)&i && j != k)
						dp[i][j] = min(dp[i][j], dp[i^(1<<j)][k]+dis[k][j]);
				}
			}
		}
		int ans = INF;
		rep(i,0,cnt) ans = min(ans,dp[ALL][i]+dis[i][cnt]);
		if(INF == ans) puts("-1");
		else printf("%d\n", ans);
	}
	return 0;
}