【NOIP2012模拟10.25】旅行

本文主要是介绍【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

Data Constraint

2<=n,m<=1000

Solution

我在比赛时大胆的提出了一个猜想：任意两个点的距离都是他们的曼哈顿距离
然而被推翻了，但是我不知道如何改进我的猜想
于是就放弃了……
实际上猜想差不多是对的，一个x和它左右比它高的x隔开的东西和这个x下面的东西距离为曼哈顿距离+2，只绕一下，然后就没了

Code

#include<cstdio>
#include<algorithm>
#include<cstring>
#define db double
#define ll long long
#define fo(i,a,b) for(ll i=a;i<=b;i++)
#define N 1010
#define abs(x) ((x)<0?-(x):(x))
using namespace std;
int a[N][N];
db ans=0,l[N],h[N],h1[N],l1[N],tot,n,m;
int main()
{scanf("%lf%lf\n",&n,&m);fo(i,1,n) h[i]=214748347;fo(i,1,m) l[i]=214748347;fo(i,1,n) {fo(j,1,m){char c;scanf("%c",&c);if(c=='X') h[i]=j,l[j]=i,a[i][j]=1;else a[i][j]=1,tot++,h1[i]++,l1[j]++;}scanf("\n");}fo(i,1,n) fo(j,i,n) ans+=(h1[i]*h1[j]*(j-i)*2.0)/tot/tot;fo(i,1,m) fo(j,i,m) ans+=(l1[i]*l1[j]*(j-i)*2.0)/tot/tot;fo(i,1,m) if(l[i]<214748347){db jy=l[i]-1; for(int j=i;j>1&&l[j-1]<l[j];j--) jy+=l[j-1]-1;for(int j=i;j<m&&l[j+1]<l[j];j++) jy+=l[j+1]-1;ans+=4.0*(n-l[i])*jy/tot/tot;}fo(i,1,n)if(h[i]<214748347){db jy=h[i]-1; for(int j=i;j>1&&h[j-1]<h[j];j--) jy+=h[j-1]-1;for(int j=i;j<n&&h[j+1]<h[j];j++) jy+=h[j+1]-1;ans+=4.0*(m-h[i])*jy/tot/tot;}printf("%.4lf\n",ans);
}