jzoj 3053. 【NOIP2012模拟10.25】旅行

Description

给定一个n行m列的字符矩阵，’.’代表空地，’X’代表障碍。移动的规则是：每秒钟以上下左右四个方向之一移动一格，不能进入障碍。

计算：在空地中随机选择起点和终点（可以重合，此时最短耗时为0），从起点移动到终点最短耗时的平均值。

每一行每一列至多有1个障碍，并且障碍不在对角线方向相邻。以下矩阵是不合法的：

.X

X.

Input

第一行两个整数n, m。

接下来n行，每行m个字符’.’或’X’。

Output

平均耗时，保留4位小数，四舍五入。

Sample Input

2 2
…
.X

Sample Output

0.8889

Hint

2<=n,m<=1000

Solution

考试是很直接地认为要求的就是每个点之间的哈夫曼距离 div 方案数。
结果后来被证实是错的了。。。
我们举个最简单的例子
...
.*.
...
上面两个加粗了的点的距离正确来说应当是4，而非2，所以，我们就发现了：
从A走到B的距离为：哈夫曼距离 or 哈夫曼距离+2。
哈夫曼距离就用O（n²+m²）先求出来，然后在特判一下要绕行的即可。
具体情况就看一看下图：（来自题解）

Code

#include<cstdio>
#define N 2010
using namespace std;
int n,m,s=0,h[N],l[N],hw[N],lw[N];
long long ans=0,ans1;
char sc[N];

int main()
{
	freopen("travel.in","r",stdin);
	freopen("travel.out","w",stdout);
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
	{
		scanf("%s",sc+1);
		for (int j=1;j<=m;j++)
			if (sc[j]=='X') h[i]++,l[j]++,s++,hw[i]=j,lw[j]=i;
	}
	for (int i=1;i<=n;i++)
		for (int j=i+1;j<=n;j++)
			ans+=(m-h[i])*(m-h[j])*(j-i);
	for (int i=1;i<=m;i++)
		for (int j=i+1;j<=m;j++)
			ans+=(n-l[i])*(n-l[j])*(j-i);
	ans<<=1;
	for (int i=1,j,t;i<=n;i++)
	{
		if (!hw[i]) continue;
		j=i;t=m-hw[i];
		while (hw[j]<hw[j+1] && hw[j+1]) j++,t+=m-hw[j];
		j=i;
		while (hw[j]<hw[j-1] && hw[j-1]) j--,t+=m-hw[j];
		ans+=(t*(hw[i]-1)<<2);
	}
	for (int i=1,j,t;i<=m;i++)
	{
		if (!lw[i]) continue;
		j=i;t=n-lw[i];
		while (lw[j]<lw[j+1] && lw[j+1]) j++,t+=n-lw[j];
		j=i;
		while (lw[j]<lw[j-1] && lw[j-1]) j--,t+=n-lw[j];
		ans+=(t*(lw[i]-1)<<2);
	}
	ans1=(long long)(n*m-s)*(n*m-s);
	printf("%.4lf
",(double)ans/ans1);
	return 0;
}