刷题总结——路径（ssoi）

题目：

题目背景

CF 57D

题目描述

小美今天和她的好朋友在玩捉迷藏游戏。
地图可以抽象成一张 n*m 的图，地图上有一些障碍。
但这些障碍有一些性质：
1：每个障碍周围 8 个格子是没有障碍的。
2：每行每列最多只有一个障碍。
每次小美会躲在一个空地上，而她的朋友小芳会在一个空地出发寻找小美。
小美想知道如果每次小芳走 4 方向的最短路来抓她，而她们俩每次都各随机选一个空地，这个路径的平均长度是多少？

输入格式

输入第一行两个整数 n 和 m 。
接下来 n 行，每行一个长为 m 的字符串表示地图。
‘.’ 表示空地，‘X’ 表示障碍。

输出格式

输出一个小数表示平均路径长度。

样例数据 1

输入　 [复制]

2 2
..
.X

输出

0.888889

样例数据 2

输入　 [复制]

3 3
...
.X.
...

输出

2.000000

备注

【数据规模】
对于 30% 的数据：n,m≤50；
对于 100% 的数据：2≤n,m≤1000。

题解：

先算竖直方向总共走的路程再算水平方向，注意算出多的路径*2；

代码：

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<ctime>
#include<cctype>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int N=1005;
char s[N];
int totx=0,n,m,liex[N],hangx[N];
long long findans(int n,int m,int a[])
{
    long long res=0;
    for(int i=1;i<=n;i++)
    {
        long long sig=0,tot=m-a[i];
        for(int j=1;j<=n;j++)
            if(a[j])sig+=(m-1)*abs(i-j);
            else sig+=m*abs(i-j);
        if(a[i])res+=(m-1)*sig;
        else res+=m*sig;
        if(a[i])
        {
            int l=i-1,r=i+1;
            while(a[l]>a[l+1])
                tot+=m-a[l],l--;
            while(a[r]>a[r-1])
                tot+=m-a[r],r++;
            res+=4*tot*(a[i]-1);
        }
    }
    return res;
}
int main()
{
  //freopen("a.in","r",stdin);
  scanf("%d%d",&n,&m);
  for(int i=1;i<=n;i++)
  {
    scanf("%s",s);
    for(int j=1;j<=m;j++)
      if(s[j-1]=='X')
      {
        hangx[i]=j;
        liex[j]=i;
        totx++;
      }
  }
  int tot=n*m-totx;
  double ans=(findans(n,m,hangx)+findans(m,n,liex))*1.0/tot/tot;
  printf("%0.6lf",ans);
  return 0;
}