Description

给定一个n行m列的字符矩阵，’.’代表空地，’X’代表障碍。移动的规则是：每秒钟以上下左右四个方向之一移动一格，不能进入障碍。

计算：在空地中随机选择起点和终点（可以重合，此时最短耗时为0），从起点移动到终点最短耗时的平均值。
每一行每一列至多有1个障碍，并且障碍不在对角线方向相邻。以下矩阵是不合法的：
.X
X.

Solution

先计算出两两点的曼哈顿距离，这个可以把x,y两个维度分开来做，维护两个变量，直接扫即可，
剩下的，我们发现如果要绕行，每个绕行只会让路程增加2，
于是我们只需要你统计有多少个需要绕行即可，
先考虑上下的绕行，绕行只存在于一个障碍的上边和下边，以及往左，往右，具体情况比较复杂，上个图：（红蓝表示要绕行的点群）大家看图生动形象理解一下吧

左右的绕行类似，
复杂度：$O(n^2)$

Code

#include
#include
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
typedef long long LL;
const int N=1050;
int read(int &n)
{char ch=' ';int q=0,w=1;for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());if(ch=='-')w=-1,ch=getchar();for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int m,n;
LL ans;
bool a[N][N];
int S[N],H[N];
int main()
{LL q,T;char ch;scanf("%d%d",&n,&m);fo(i,1,n)fo(j,1,m){for(ch=getchar();ch!='.'&&ch!='X';ch=getchar());if(ch=='X')a[i][j]=1,S[i]=j,H[j]=i;}q=T=0;fo(i,1,n){fo(j,1,m)if(!a[i][j])ans+=q,T++;q+=T;}q=T=0;fo(i,1,m){fo(j,1,n)if(!a[j][i])ans+=q,T++;q+=T;}fo(i,1,n)if(S[i]){q=0;for(int j=i;j>0&&S[j]>q;j--)q=S[j],ans+=2*(m-q)*(S[i]-1);q=S[i];for(int j=i-1;j>0&&S[j]2*(q-1)*(m-S[i]);}fo(i,1,m)if(H[i]){q=0;for(int j=i;j>0&&H[j]>q;j--)q=H[j],ans+=2*(n-q)*(H[i]-1);q=H[i];for(int j=i-1;j>0&&H[j]2*(q-1)*(n-H[i]);}printf("%.4lf\n",(double)2*ans/(T*T));return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！