自动搬运

查看原文

来自洛谷，原作者为

	Gavin·Olivia **

搬运于2025-08-24 21:44:59，当前版本为作者最后更新于2018-10-31 20:09:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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

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

预处理第一步：

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

预处理第二步：

$BFS$处理岛屿之间的距离，$d[i][j]$表示从岛屿$i$到岛屿$j$最少经过几片浅水区。对于岛屿$i$，现将属于它的陆地都入队，然后$BFS$扩展全图，这里有一个小技巧，我们开一个双端队列，对于下一个未访问过的点，如果它是陆地，就把它放到队头；如果是浅水区，就把它放到队尾。如果不用双端队列，就只能入队浅水区，并且之后还要再$SPFA$处理一次。

双端队列证明：

对于队头点$(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;
}