【NOIP2012模拟10.25】旅行

題目

給定一個n行m列的字元矩陣，’.’代表空地，’X’代表障礙。移動的規則是：每秒鐘以上下左右四個方向之一移動一格，不能進入障礙。

計算：在空地中随機選擇起點和終點（可以重合，此時最短耗時為0），從起點移動到終點最短耗時的平均值。

每一行每一列至多有1個障礙，并且障礙不在對角線方向相鄰。以下矩陣是不合法的：

.X

X.

分析

50%的資料，全都是空地，答案就是所有兩點間的曼哈頓距離和。

很容易求， 第i行空地的數量∗第j行空地的數量∗|i−j|∗2

因為每一行每一列至多有1個障礙，并且障礙不在對角線方向相鄰。得出從A走到B的耗時，要麼等于AB的曼哈頓距離，要麼等于AB的曼哈頓距離+2。

現在考慮什麼情況下距離加二。

觀察下圖，規律顯而易見，我就不多說了，

#include <cmath>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <queue>
const int maxlongint=;
const int mo=;
const int N=;
using namespace std;
int a[N][N],n,m,sum,sx[N],sy[N],xx[N],xy[N];
double ans;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++)
        {
            char c=getchar();
            while(c!='.' && c!='X') c=getchar();
            if(c=='.')
            {
                sx[i]++;
                sy[j]++;
                sum++;
            }
            else
            {
                xx[i]=j;
                xy[j]=i;    
            }
        }
    for(int i=;i<=n;i++)
        for(int j=;j<=n;j++)
            ans+=abs(i-j)*sx[i]*sx[j]*/sum/sum;
    for(int i=;i<=m;i++)
        for(int j=;j<=m;j++)
            ans+=abs(i-j)*sy[i]*sy[j]*/sum/sum;
    for(int i=;i<=n;i++)
    if(xx[i])
    {
        int mn=maxlongint,mx=-;
        for(int j=i;j>=;j--)
        {
            if(xx[j]>mx && xx[j])
            {
                ans+=*(xx[i]-)*(m-xx[j])*/sum/sum;
                mx=xx[j];
            }
            else
            break;
        }
        for(int j=i;j>=;j--)
        {
            if(xx[j]<mn && xx[j])
            {
                ans+=*(xx[j]-)*(m-xx[i])*/sum/sum;
                mn=xx[j];
            }
            else
            break;
        }
        mn=xx[i],mx=xx[i];
        for(int j=i+;j<=n;j++)
        {
            if(xx[j]>mx && xx[j])
            {
                ans+=*(xx[i]-)*(m-xx[j])*/sum/sum;
                mx=xx[j];
            }
            else
            break;
        }
        for(int j=i+;j<=n;j++)
        {
            if(xx[j]<mn && xx[j])
            {
                ans+=*(xx[j]-)*(m-xx[i])*/sum/sum;
                mn=xx[j];
            }
            else
            break;
        }
    }
    for(int i=;i<=m;i++)
    if(xy[i])
    {
        int mn=maxlongint,mx=-;
        for(int j=i;j>=;j--)
        {
            if(xy[j]>mx && xy[j])
            {
                ans+=*(xy[i]-)*(n-xy[j])*/sum/sum;
                mx=xy[j];
            }
            else
            break;
        }
        for(int j=i;j>=;j--)
        {
            if(xy[j]<mn && xy[j])
            {
                ans+=*(xy[j]-)*(n-xy[i])*/sum/sum;
                mn=xy[j];
            }
            else
            break;
        }
        mn=xy[i],mx=xy[i];
        for(int j=i+;j<=m;j++)
        {
            if(xy[j]>mx && xy[j])
            {
                ans+=*(xy[i]-)*(n-xy[j])*/sum/sum;
                mx=xy[j];
            }
            else
            break;
        }
        for(int j=i+;j<=m;j++)
        {
            if(xy[j]<mn && xy[j])
            {
                ans+=*(xy[j]-)*(n-xy[i])*/sum/sum;
                mn=xy[j];
            }
            else
            break;
        }
    }
    printf("%.4lf",ans);
}