有一个n*m的棋盘，上面有一些棋子，每行每列最多只会有一个棋子，不会有两个棋子八连通。问随机一个空格子作为起点，再随机地选择一个空格子作为终点，求问不经过任意棋子最短路的期望长度是多少。多组，n,m<=2000。
首先答案分子显然是所有点对距离之和，分母就是不是棋子的位置个数的平方。
假装没有棋子，那么距离就是曼哈顿距离了。那么我们可以考虑将x项和y项分开统计，所以只要按x、y坐标顺序枚举点即可。
现在有了棋子，我们考虑哪些东西会受到影响。
①同一行/同一列的被棋子隔开，这样肯定距离要加2。
②那不是同一行，同一列呢？
经过一番思考，我们可以发现对于一个蓝色位置的格子，只有红色位置的格子到这个点距离要加2。
我来解释一下...就是说首先要是连续的一串列都有障碍，然后障碍的位置还要是单调的。
这样我们就模拟一下就行了。似乎也不是特别难写。
#include <iostream> #include <stdio.h> #include <stdlib.h> #include <string.h> using namespace std; #define S 1004 int T,n,m,hang[S],lie[S]; typedef long long ll; char cs[S][S]; void sol() { memset(hang,0,sizeof(hang)); memset(lie,0,sizeof(lie)); ll cnt=0; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%s",cs[i]+1); for(int j=1;j<=m;j++) { if(cs[i][j]==‘G‘) hang[i]=j, lie[j]=i; else ++cnt; } } long long sum=0; //hang { long long s=0,c=0; for(int i=1;i<=n;i++) { long long cur=m-(bool)hang[i]; sum+=(i*c-s)*cur; s+=i*cur; c+=cur; } } //lie { long long s=0,c=0; for(int j=1;j<=m;j++) { long long cur=n-(bool)lie[j]; sum+=(j*c-s)*cur; s+=j*cur; c+=cur; } } for(int i=1;i<=n;i++) if(hang[i]) sum+=(hang[i]-1)*(ll)(m-hang[i])*2; for(int i=1;i<=m;i++) if(lie[i]) sum+=(lie[i]-1)*(ll)(n-lie[i])*2; //hang { for(int s=0;s<=1;s++) { long long ss=0; for(int i=1;i<=n;i++) { if(!hang[i]) {ss=0; continue;} if(hang[i-1]&&(hang[i]>hang[i-1])==s) sum+=ss*((!s)?(hang[i]-1):(m-hang[i])); else ss=0; ss+=((s)?(hang[i]-1):(m-hang[i]))*2; } } } //lie { for(int s=0;s<=1;s++) { long long ss=0; for(int i=1;i<=m;i++) { if(!lie[i]) {ss=0; continue;} if(lie[i-1]&&(lie[i]>lie[i-1])==s) sum+=ss*((!s)?(lie[i]-1):(n-lie[i])); else ss=0; ss+=((s)?(lie[i]-1):(n-lie[i]))*2; } } } cnt*=cnt; sum*=2; printf("%.4lf\n",sum/(double)cnt); } int main() { freopen("chess.in","r",stdin); freopen("chess.out","w",stdout); scanf("%d",&T); while(T--) sol(); }
原文：http://www.cnblogs.com/zzqsblog/p/5719366.html