本文共 1413 字，大约阅读时间需要 4 分钟。

题目链接：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
   
    #include
    
     #include
     
      #include
      
       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
       
        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
        
          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]
        
       
      
     
    
   

转载地址：http://hhuvi.baihongyu.com/