有一个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();
}