acm Sheep Frenzy(状态压缩+BFS)

题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=12511

题目大意：给定一个矩阵：“#”代表绵羊，“X”代表山不能走，‘’。‘代表草坪能走；“U”代表起始点；问从起始点开始，能否把所有的绵羊都吃掉，

如果能问，最好花多少时间？

解题报告人：GHQ（SpringWater）

解题思路：考虑到绵羊的总是最多为16，将开始点考虑进去共17个点，所以只用先用BFS求出这17个点的相互距离，之后再利用状态压缩，

dp【i】【j】=min(dp【i】【j】,dp【i^(1<<j)】【k】+dis【j】【k】+1);表示，在状态i下，j最后访问，的最小时间消费值；

最终的ans=min（dp【up】【j】）

代码如下：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<queue>
using namespace std;
const int S = (1 << 17);
const int inf = 1<<29;
char mat[55][55];
int rem[20], cnt, dis[20][20];
int d[55][55];
int dx[]={0,0,-1,1};
int dy[]={-1,1,0,0};
int dp[S][17];
int N,M;
bool isok(int x,int y)
{
	if(x<0||y<0||x>=N||y>=M||mat[x][y]=='X')return false;
	return true;
}
void bfs(int x,int y)
{
	int tx,ty,i,j;
	int xx = x;
	int yy = y;
	queue<int>qx,qy;
	qx.push(x);
	qy.push(y);
	for(i = 0; i < N; ++ i)
		for(j = 0; j < M; ++ j)
			d[i][j]=inf;
	d[x][y]=0;
	while(!qx.empty()){
		x = qx.front(); qx.pop();
		y = qy.front(); qy.pop();
		for(i = 0; i < 4; ++ i){
			tx = x + dx[i];
			ty = y + dy[i];
			if(!isok(tx,ty)||d[x][y]+1>=d[tx][ty])continue;
			d[tx][ty] = d[x][y] + 1;
			qx.push(tx);
			qy.push(ty);
		}
	}
}
int min(int a,int b)
{
	return (a<b)?a:b;
}
void DP(int up)
{
	int i, k,j;
	int temp = (up<<1)|1;
	for(k=0;k<=temp;k++)
	for(i = 0; i <=cnt; i++)dp[k][i] = inf;
	dp[1][0] = 0;
	for(i = 1; i <= up ; ++ i)
	{
		temp = (i<<1)|1;
		for(j = 1; j <= cnt; j++)
		{
			if(temp&(1<<j))
			{
				for(k = 0; k <= cnt ;k ++)
				{
					if(k!=j)
						dp[temp][j] =min(dp[temp][j],dp[temp^(1<<j)][k]+dis[j][k]+1);
				}
			}
		}
	}
}
int main()
{
	int T, i, j, ans, up;
	for(scanf("%d", &T); T--; )
	{
		scanf("%d%d",&N, &M);
		for(cnt = i = 0; i < N; i++)
		{
			scanf("%s",mat[i]);
			for(j = 0; j < M; j++)
			{
				if(mat[i][j]=='#')
					rem[++cnt] = i * M + j;
				if(mat[i][j]=='U')
					rem[0] = i * M + j;
			}
		}

		bfs(rem[0]/M, rem[0]%M);
		for(i = 1; i <= cnt; i++)
		{
			if(d[rem[i]/M][rem[i]%M] == inf)
				break;
			else
				dis[0][i] =dis[i][0] = d[rem[i]/M][rem[i]%M];
		}
		if(i > cnt)
		{
			for(i = 1; i <= cnt; i++)
			{
				bfs(rem[i]/M, rem[i]%M);
				for(j = 1; j <= cnt; j++)
					dis[j][i]=dis[i][j]=d[rem[j]/M][rem[j]%M];
			}
			up = ( 1 << (cnt) ) - 1;
			DP(up);
			up=(up<<1)|1;
			for(i=0, ans = inf; i <= cnt; i++)
			{
				if(dp[up][i]<ans)
					ans=dp[up][i];
			}
			printf("%d\n",ans);
		}
		else
			printf("impossible\n");
	}
	return 0;
}