第二题：旅行(journey)
时间限制：1秒
内存限制：256MB
输入：journey.in
输出：journey.out
问题描述
给定一个n行m列的字符矩阵，’.’代表空地，’X’代表障碍。移动的规则是：每秒钟以上下左右四个方向之一移动一格，不能进入障碍。计算：在空地中随机选择起点和终点（可以重合，此时最短耗时为0），从起点移动到终点最短耗时的平均值。
每一行每一列至多有1个障碍，并且障碍不在对角线方向相邻。以下矩阵是不合法的：
.X
X.
输入
第一行两个整数n, m。。
接下来n行，每行m个字符’.’或’X’。在50%的数据中，保证每个字符都是’.’。
输出
平均耗时，保留4位小数，四舍五入。数据保证在范围之内输出一致，Ans是标准答案。
样例输入
2 2
..
.X
样例输出
0.8889
yle�� sth�p�ive;top:3.0pt;mso-text-raise:-3.0pt'>。所有信息按照从左到右的顺序给出。在50%的数据中，。
输出
第一行：出列的总对数k。接下来输出k行，每行是两个整数。按跳舞顺序输出，两个整数代表这一对舞伴的编号（按输入顺序从左往右1至n编号）。请先输出较小的整数，再输出较大的整数。
样例输入
4
BGBG
4 2 4 3
样例输出
2
3 4
1 2
样例输入
4
BGBB
1 1 2 3
样例输出
1
1 2
解1：
Dp出所有平地曼哈顿距离和（全T）
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
#include<stack>
using namespace std;
#define MAXN (1000+10)
#define DELTA (0.00000001)
#define F (10000000)
int n,m;
char s[2000];
int a[MAXN],b[MAXN];
long long f[MAXN][MAXN];
int calc(int l,int r,int n)
{
return 2*(l-1)*(n-r);
}
int main()
{
freopen("journey.in","r",stdin);
freopen("journey.out","w",stdout);
/* long long ans=0;
scanf("%d%d",&n,&m);
for (int n=1;n<=10;n++)
{
for (int m=1;m<=10;m++)
{
long long ans=0;
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
for (int k=1;k<=n;k++)
for (int l=1;l<=m;l++)
ans+=abs(i-k)+abs(j-l);
printf("%d ",ans);
}
cout<<endl;
}
*/
memset(f,0,sizeof(f));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
long long tot=0;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%s",s);
for (int j=0;j<m;j++)
if (s[j]=='X')
{
tot++;
a[i]=j+1;
b[j+1]=i;
break;
}
}
tot=n*m-tot;
// for (int i=1;i<=n;i++) cout<<a[i]<<' ';
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+i*j*(i+j-2)+(i-1)*(j-1)*(i+j);
if (a[i]==j) f[i][j]-=+i*j*(i+j-2);
else
{
for (int k=1;k<=i;k++)
if (a[k]&&a[k]<=j)
f[i][j]-=2*(i-k+j-a[k]);
if (a[i]&&a[i]<j)
f[i][j]-=(i-1)*(i+2*(j-a[i]));
if (b[j]&&b[j]<i)
f[i][j]-=(j-1)*(j+2*(i-b[j]));
if (a[i]&&a[i]<j&&b[j]&&b[j]<i)
f[i][j]+=2*((j-a[i])+(i-b[j]));
}
// cout<<f[i][j]<<endl;
}
/*
for (int i=0;i<=n;i++){
for (int j=0;j<=m;j++)
cout<<f[i][j]<<' ';
cout<<'n';
}*/
long long ans=f[n][m];
// cout<<ans<<endl;
for (int i=1;i<=n;i++)
if (a[i])
{
ans+=2*calc(a[i],a[i],m);
if (i>1&&a[i-1])
{
int j=i-1;
if (a[j]<a[j+1])
{
while (j>0&&a[j]&&a[j]<a[j+1]) {ans+=2*calc(a[j],a[i],m);j--;}
}/*
else if (a[j]>a[j+1])
{
while (j>0&&a[j]>a[j+1]) {ans+=2*calc(a[i],a[j],m);j--;}
} */
}
if (i<n&&a[i+1])
{
int j=i+1;
if (a[j]<a[j-1])
{
while (j<=n&&a[j]&&a[j]<a[j-1]) {ans+=2*calc(a[j],a[i],m);j++;}
}/*
else if (a[j]>a[j-1])
{
while (j<=n&&a[j]>a[j-1]) {ans+=2*calc(a[i],a[j],m);j++;}
}*/
}
}
for (int i=1;i<=m;i++)
if (b[i])
{
ans+=2*calc(b[i],b[i],n);
if (i>1&&b[i-1])
{
int j=i-1;
if (b[j]<b[j+1])
{
while (j>0&&b[j]&&b[j]<b[j+1]) {ans+=2*calc(b[j],b[i],n);j--;}
}/*
else if (b[j]>b[j+1])
{
while (j>0&&b[j]>b[j+1]) {ans+=2*calc(b[i],b[j],n);j--;}
}*/
}
if (i<m&&b[i+1])
{
int j=i+1;
if (b[j]<b[j-1])
{
while (j<=m&&b[j]&&b[j]<b[j-1]) {ans+=2*calc(b[j],b[i],n);j++;}
}/*
else if (b[j]>b[j-1])
{
while (j<=m&&b[j]>b[j-1]) {ans+=2*calc(b[i],b[j],n);j++;}
}*/
}
}
// cout<<ans<<endl;
double _ans=double(ans)/double(tot)/double(tot);
printf("%.4lfn",_ans);
while (1);
return 0;
}
正解
找一格，向前后搜 曼哈顿距离和分别考虑纵横方向
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<functional>
#include<algorithm>
#include<stack>
using namespace std;
#define MAXN (1000+10)
#define DELTA (0.00000001)
#define F (10000000)
int n,m;
char s[2000];
int a[MAXN],b[MAXN];
//long long f[MAXN][MAXN];
int calc(int l,int r,int n)
{
return 2*(l-1)*(n-r);
}
int main()
{
freopen("journey.in","r",stdin);
freopen("journey.out","w",stdout);
// memset(f,0,sizeof(f));
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
long long tot=0;
scanf("%d%d",&n,&m);
for (int i=1;i<=n;i++)
{
scanf("%s",s);
for (int j=0;j<m;j++)
if (s[j]=='X')
{
tot++;
a[i]=j+1;
b[j+1]=i;
break;
}
}
tot=n*m-tot;
// for (int i=1;i<=n;i++) cout<<a[i]<<' ';
/*
for (int i=1;i<=n;i++)
for (int j=1;j<=m;j++)
{
f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+i*j*(i+j-2)+(i-1)*(j-1)*(i+j);
if (a[i]==j) f[i][j]-=+i*j*(i+j-2);
else
{
for (int k=1;k<=i;k++)
if (a[k]&&a[k]<=j)
f[i][j]-=2*(i-k+j-a[k]);
if (a[i]&&a[i]<j)
f[i][j]-=(i-1)*(i+2*(j-a[i]));
if (b[j]&&b[j]<i)
f[i][j]-=(j-1)*(j+2*(i-b[j]));
if (a[i]&&a[i]<j&&b[j]&&b[j]<i)
f[i][j]+=2*((j-a[i])+(i-b[j]));
}
// cout<<f[i][j]<<endl;
}
/*
for (int i=0;i<=n;i++){
for (int j=0;j<=m;j++)
cout<<f[i][j]<<' ';
cout<<'n';
}*/
long long ans=0;
for (int i=1;i<n;i++)
for (int j=i+1;j<=n;j++)
ans+=(m-(a[i]>0))*(m-(a[j]>0))*(j-i);
for (int i=1;i<m;i++)
for (int j=i+1;j<=m;j++)
ans+=(n-(b[i]>0))*(n-(b[j]>0))*(j-i);
ans*=2;
// long long ans=f[n][m];
// cout<<ans<<endl;
for (int i=1;i<=n;i++)
if (a[i])
{
ans+=2*calc(a[i],a[i],m);
if (i>1&&a[i-1])
{
int j=i-1;
if (a[j]<a[j+1])
{
while (j>0&&a[j]&&a[j]<a[j+1]) {ans+=2*calc(a[j],a[i],m);j--;}
}
}
if (i<n&&a[i+1])
{
int j=i+1;
if (a[j]<a[j-1])
{
while (j<=n&&a[j]&&a[j]<a[j-1]) {ans+=2*calc(a[j],a[i],m);j++;}
}
}
}
for (int i=1;i<=m;i++)
if (b[i])
{
ans+=2*calc(b[i],b[i],n);
if (i>1&&b[i-1])
{
int j=i-1;
if (b[j]<b[j+1])
{
while (j>0&&b[j]&&b[j]<b[j+1]) {ans+=2*calc(b[j],b[i],n);j--;}
}
}
if (i<m&&b[i+1])
{
int j=i+1;
if (b[j]<b[j-1])
{
while (j<=m&&b[j]&&b[j]<b[j-1]) {ans+=2*calc(b[j],b[i],n);j++;}
}
}
}
// cout<<ans<<endl;
double _ans=double(ans)/double(tot)/double(tot);
printf("%.4lfn",_ans);
// while (1);
return 0;
}
