旅行（HG 2018.7.7 T2）

### 【问题描述】 给定一个n 行m 列的字符矩阵，‘.’表示空地，‘X’表示障碍。移动的规则是：每秒钟可以上下 左右四个方向之一移动一格，不能进入障碍。计算：在空地中随机选择起点和终点（可以重合，此时 最短耗时为0），从起点移动到终点最短耗时的平均值。 每一行每一列至多有1 个障碍，并且障碍不在对角线方向相邻。以下矩阵是不合法的： .X X. ### 【输入】 每一行两个整数n，m。 接下来n 行，每行m 个字符‘.’或‘X’。在50%的数据中，保证每个字符都是‘.’。 ### 【输出】 输出平均耗时，四舍五入保留4位小数。数据保证在[ans-10^7,ans+10^7]范围之内输出一致， ans 是标准答案。 ### 【输入样例】 2 2 .. .X ### 【输出样例】 0.8889 ### 【Hint】 若有p 个空地，则随机选择起点到终点最短耗时的平均值为任意两点间曼哈顿距离之和除以空地总数的平方 ------------ 对于不需要绕过x的情况，我们只用加上这两点的曼哈顿距离*2 需要绕的情况，需要额外走2步：  也就是连着几行或级列x的位子上升或下降 我们只用先算出所有点不绕路的总曼哈顿值，再加上绕路的值即可 ------------ ```cpp #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int n,m; double sum=0,num=0; int l[1100],p[1100];//记录每行每列有几个空地 int x[1100],y[1100];//记录第i行的x在第几列，第j列的x在第几行 int main() { memset(l,0,sizeof(l)); memset(p,0,sizeof(p)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { char tmp[1100]; scanf("%s",tmp+1); for(int j=1;j<=m;j++) { if(tmp[j]=='.') num++,l[i]++,p[j]++; else x[i]=j,y[j]=i; } } for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++) sum+=2*(j-i)*l[i]*l[j]; for(int i=1;i<m;i++) for(int j=i+1;j<=m;j++) sum+=2*(j-i)*p[i]*p[j];//按照不绕路处理 for(int i=1;i<=n;i++) { if(x[i]) { int up=x[i]-1,don=m-x[i],k=i; if(x[i+1]<x[i]) { while(x[k+1]<x[k] && x[k+1] && k<n) up+=x[k+1]-1,k++; sum+=4.0*up*don; } else { while(x[k+1]>x[k] && x[k+1] && k<n) don+=m-x[k+1],k++; sum+=4.0*up*don; } } } for(int i=1;i<=m;i++) { if(y[i]) { int up=y[i]-1,don=n-y[i],k=i; if(y[i+1]<y[i]) { while(y[k+1]<y[k] && y[k+1] && k<m) up+=y[k+1]-1,k++; sum+=4.0*up*don; } else { while(y[k+1]>y[k] && y[k+1] && k<m) don+=n-y[k+1],k++; sum+=4.0*up*don; } } }//加上绕路的值 printf("%.4lf",sum/(num*num)); return 0; } ```