题解 P3070 【[USACO13JAN]岛游记Island Travels】

· · 题解

非正式宣布，我和USACO的DP杠上了

这题的预处理是动规主体的10倍不止呢……严重怀疑它被评为蓝题不是因为动规难而是因为预处理烦。

预处理第一步：

把整张图BFS跑一遍，找出所有岛屿并打上标记，num[i][j]表示陆地(i,j)属于第几个岛屿。

预处理第二步：

#### 双端队列证明： 对于队头点$(i,j)$，它的值为$len$，则在队列中的点的值要么是$len$，要么是$len+1$。如果下一个点是陆地，则它的值是$len$，否则是$len+1$。显然前者扩展出的状态会比后者更优，因此将前者放于队头，优先扩展。 ### 预处理第三步： 如果之前有用过双端队列，就可以省略这一步，不然还要再跑$n$遍的$SPFA$求岛屿之间的最短路。我是懒得打了啦……如果有大佬打出来了，还请私信发给我，让蒟蒻%%%。 ### $DP

（相对于预处理来说）状压就变得特别好写，简直是在送分。f[i][j]表示经过岛屿状态为i、最后到达的岛屿编号为j时经过浅水区的最少数量。动态转移方程

f[i|(1<<(k-1))][k]=min(f[i][j]+d[j][k])

以上具体实现过程详见代码。

#include<bits/stdc++.h>
 using namespace std;
 int fx[4]={-1,1,0,0};
 int fy[4]={0,0,-1,1};
 int n,m,i,j,k,cnt,l,r,lim,ans,maxn;
 int c[20],f[33000][17];
 int num[55][55],d[20][20];
 int x[5005],y[5005],dis[5005];
 bool used[55][55];
 char s[55][55];
 inline int read()
{
    int x=0,c; bool f=0;
    for(;(c=getchar())<'0'||c>'9';f|=c=='-');
    for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+c-48;
    return f?-x:x;
}
 void land_f()//预处理第一步
{
    int a,b,xx,yy,i;
    while(l<=r)
    {
        a=x[l]; b=y[l++];
        for(i=0;i<4;i++)
        {
            xx=a+fx[i]; yy=b+fy[i];
            if(xx<=0||yy<=0||xx>n||yy>m||used[xx][yy]||s[xx][yy]!='X') continue;
            used[xx][yy]=true; num[xx][yy]=cnt;
            x[++r]=xx; y[r]=yy;
        }
    }
}
 void land_c(int now)//预处理第二步
{
    int a,b,c,xx,yy,i;
    while(l<=r)
    {
        a=x[l]; b=y[l]; c=dis[l++];
        for(i=0;i<4;i++)
        {
            xx=a+fx[i]; yy=b+fy[i];
            if(xx<=0||yy<=0||xx>n||yy>m||used[xx][yy]||s[xx][yy]=='.') continue;
            used[xx][yy]=true; 
            if(s[xx][yy]=='X')
            {
                if(d[now][num[xx][yy]]<0)
                 d[now][num[xx][yy]]=c;
                x[--l]=xx; y[l]=yy; dis[l]=c;
                continue;
            }
            x[++r]=xx; y[r]=yy; dis[r]=c+1;
        }
    }
}
 int main()
{
    n=read(); m=read();
    for(i=1;i<=n;i++) scanf("%s",s[i]+1);
    for(i=1;i<=n;i++)
     for(j=1;j<=m;j++)
      if(s[i][j]=='X'&&(!used[i][j]))
      {
        ++cnt; l=r=1; x[1]=i; y[1]=j;
        used[i][j]=true; num[i][j]=cnt;
        land_f();
      }
    maxn=n*m; memset(d,-1,sizeof(d));
    for(k=1;k<=cnt;k++)
    {
        l=maxn+1; r=maxn; d[k][k]=0;
        for(i=1;i<=n;i++) for(j=1;j<=m;j++)
        {
            used[i][j]=false;
            if(num[i][j]==k)x[++r]=i,y[r]=j,dis[r]=0,used[i][j]=true;
        }
        land_c(k);
    }
    lim=(1<<cnt)-1; memset(f,63,sizeof(f)); 
    for(i=1;i<=cnt;i++) c[i]=1<<i-1,f[c[i]][i]=0;
    for(i=1;i<lim;i++)
    {
        for(j=1;j<=cnt;j++)
         if((i&c[j])&&f[i][j]<maxn)
          for(k=1;k<=cnt;k++)
           if(!(i&c[k])&&d[j][k]>0)//如果d[j][k]=-1,说明岛屿j和岛屿k不连通
            f[i|c[k]][k]=min(f[i|c[k]][k],f[i][j]+d[j][k]);
    }
    ans=1e9;
    for(i=1;i<=cnt;i++) ans=min(ans,f[lim][i]);
    printf("%d",ans);
    return 0;
}