描述
在一个n行m列的矩阵中，’P’代表平缓的场地，’H’代表小山。人的起点是在某个P的空格中，在这个矩阵中移动的规则如下：
每秒钟人可以向上下左右四个方向中任何一个方向移动一格，但需要注意的是不能进入小山所在的格子。
现在在P中随机选择起点和终点（起点和终点是可以重合的，如果重合则耗时为0），请你计算从起点移动到终点的最短耗时的平均值。
给你的矩阵有一个特点，每一行每一列至多有1个H格，并且H格不在对角线方向相邻。即给你数据中不会存在以下矩阵格式的矩阵：
PH
HP
输入
输入数据格式：
第一行两个整数n, m。
接下来n行，每行m个字符’P’或’H’。
输出
输出平均耗时值，请保留4位小数，需要四舍五入。
输入样例 1
2 2 PH PP
输出样例 1
0.8889
输入样例 2
3 3 PPP HPP PPP
输出样例 2
1.8438
提示
2<=n,m<=1000
思路（详见代码）代码：
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1010;
const int oo=1e9;
int n,m;
double ans,p;
char a[N][N];
double b[N],c[N],d[N],e[N];
int main () {
//freopen("zdl.in","r",stdin);
//freopen("zdl.out","w",stdout);
scanf("%d%d\n",&n,&m);//一定要加\n!!!
for (int i=1; i<=n; i++)
d[i]=2147483647;
for (int i=1; i<=m; i++)
e[i]=2147483647;//memset只能赋0
for(int i=1; i<=n; i++) {//n行
for(int j=1; j<=m; j++) {//m列
scanf("%c",&a[i][j]);//输入每个字符
if(a[i][j]==‘P‘) {
p++;//统计有多少个空地
b[i]++;//统计第i行有多少块空地
c[j]++;//统计第j列有多少块空地
} else {
d[i]=j;//记录障碍所在的位置
e[j]=i;
}
}
scanf("\n");//一定要加\n!!!
}
//先计算任意两点间的曼哈顿距离，这个距离分成两部分计算，
//下面这个是先计算任意两行中两个点之间的y2-y1的距离
for(int i=1; i<=n; i++)
for(int j=1; j<=n; j++)
ans+=b[i]*b[j]*abs(i-j);
//下面这个是先计算任意两列中两个点之间的x2-x1的距离
for(int i=1; i<=m; i++)
for(int j=1; j<=m; j++)
ans+=c[i]*c[j]*abs(i-j);
for(int i=1; i<=m; i++)
if(e[i]<2147483647) {//说明该列上有障碍 e[i]里保存的是该列上的障碍是在哪一行
int t=e[i]-1,k=i;//t是障碍所在行的上一行
while(k>1&&e[k-1]<e[k]) {//不是第一列，且左边那一列的障碍比当前列的障碍高
k--;//向左边列查找
t+=e[k]-1;//这一列上面有t个点，这些点到障碍所在位置的下面的所有的点距离都要加2
}
k=i;
while(k<m&&e[k+1]<e[k]) {//不是最后一列，且右边那一列的障碍比当前列的障碍高
k++;//向右边列查找
t+=e[k]-1;
}
ans+=(n-e[i])*t*4;//n-e[i]表示障碍下面有多少个点
}
for(int i=1; i<=n; i++)
if(d[i]<2147483647) {
int t=d[i]-1,k=i;
while(k>1&&d[k-1]<d[k]) {
k--;
t+=d[k]-1;
}
k=i;
while(k<n&&d[k+1]<d[k]) {
k++;
t+=d[k]-1;
}
ans+=(m-d[i])*t*4;
}
printf("%.4lf",ans/p/p);
return 0;
}
原文：https://www.cnblogs.com/mysh/p/11306524.html