文章目录

Nuts for nuts… UVA - 10944

题意：

n*m的方格中，有一个起点和num个核桃，问把所有的核桃都取了，然后回到原地的最小步数，可以往八个方向移动

分析：

先把起点和核桃都从图中抠出来，然后两两之间的距离是 M a p [ i ] [ j ] = m a x ( x [ i ] − x [ j ] , y [ i ] − y [ j ] ) Map[i][j] = max(x[i]-x[j],y[i]-y[j]) Map[i][j]=max(x[i]−x[j],y[i]−y[j]),之后状态压缩dp
dp[i][j] 代表最后一个取的核桃编号是i，现在的状态是j，j的二进制为1，代表相应编号的核桃已经取过
假设当前状态是i,j
那么它可以更新的状态是 d p [ k ] [ j ∣ ( 1 &lt; &lt; k ) − 1 ] dp[k][j|(1&lt;&lt;k)-1] dp[k][j∣(1<<k)−1] 其中 j&(1<<k)-1 == 0
d p [ k ] [ j ∣ ( ( ( 1 &lt; &lt; k ) − 1 ) ] = m i n ( d p [ k ] [ j ∣ ( ( ( 1 &lt; &lt; k ) − 1 ) ] , d p [ i ] [ j ] + M a p [ i ] [ k ] dp[k][j |(((1&lt;&lt;k)-1)] = min(dp[k][j |(((1&lt;&lt;k)-1)] ,dp[i][j]+Map[i][k] dp[k][j∣(((1<<k)−1)]=min(dp[k][j∣(((1<<k)−1)],dp[i][j]+Map[i][k]

参考代码

const int maxn = 30;
const int maxm = 1<<16;

int dp[maxn][maxm];
char s[maxn];
int  Map[maxn][maxn];
int x[maxn],y[maxn];
int num,n,m,ans,maxz;
int main(void){
  while(~scanf("%d%d",&n,&m)){
    num = 0;
    // getchar();
    for(int i = 0;i < n; ++i){
      scanf(" %s",s);
      for(int j = 0;j < m; ++j){
        if(s[j] == 'L')
          x[0] = i,y[0] = j;
        else if(s[j] == '#')
          x[++num] = i,y[num] = j;
      }
    }
    // cout<<"DEBUG"<<endl;
    if(num == 0){
      cout<<0<<endl;
      continue;
    }
    for(int i = 0;i <= num; ++i){
      for(int j = 0;j <= num; ++j){
        Map[i][j] = max(abs(x[i]-x[j]),abs(y[i]-y[j]));
        // cout<<Map[i][j]<<endl;
      }
    }
    maxz = (1<<num)-1;
    // cout<<maxz<<endl;
    for(int i = 0;i <= num;++i)
      for(int j = 0;j <= maxz; ++j)
        dp[i][j] = INF/10;
    for(int i = 1;i <= num; ++i)
      dp[i][1<<(i-1)] = Map[0][i];
    // DEBUG;
    // cout<<num<<endl;
    for(int i = 0;i <= maxz; ++i){

        for(int j = 1;j <= num; ++j){
          int result = i&(1<<(j-1));
          if(result == 0){
            result = i|(1<<(j-1));
           for(int  k = 1;k <= num; ++k){
            dp[j][result] = min(dp[j][result],dp[k][i]+Map[k][j]);
           }
          }
        }
    }
    // DEBUG;
    int ans = INF;
    for(int i = 1;i <= num; ++i)
      ans = min(ans,dp[i][maxz]+Map[i][0]);
    cout<<ans<<endl;
  }
  return 0;
}