题目链接：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;
}