 /**//*
题意:n,m的网格,有一些static particles,规定任意两个不能在同一行、列,不能在相邻的对角线
A dynamic particle选择非static的cell作为起点和终点,然后从起点选择最短路径走到终点(不经过
static particles)。问平均路长

参见解题报告:http://www.codeforces.com/blog/entry/1171
题目的那种规定,发现,对于同一行、列,如果要跨过那个'X',就需要多加2
而对于连续行的'X',如下图:
1..X ..
2 .X
3 X.
1的左边到1、2、3的右边需要多加2
2的左边到2、3的右边也需要多加2

另外,对于下图:
1..X ..
2 X.
3 .X
1的左边到2的右边需多加2,而到3的右边不需加
2的右边到3的左边需多加2
所以,从上往下,对于连续的行,寻找递增或递减的一块,然后对于这一连续的块,统计从左边到右边
或右边到左边需要多加的步数2
解题报告的框架,两两点距离之和(包括'X')- 'X'到所有点距离和*2 + 'X'到'X'距离和*2
这里多减了2倍'X'到'X'的,所以要加上
最后,再加上因为'X'存在要绕路需要多加的距离
*/

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int MAXN = 1011;

char field[MAXN][MAXN];
int row[MAXN] , col[MAXN];

__int64 solve(int n , int m , int row[])//逐行扫,寻找连续的块
  {
__int64 ans = 0 , i;
for(i = 1 ; i <= n ; i++)
 {
if(row[i] == -1)continue;

int last = 0 , start = i , end;
while(i<=n && row[i] !=-1 && row[i] > last)
 {
last = row[i];
i++;
}
end = --i;
for(int f = start ; f <= end; f++)
for(int s = f ; s <= end; s++)
ans += 2*(f==s?1:2)*(row[f]-1)*(m-row[s]);
}

for(i = 1 ; i <= n ; i++)
 {
if(row[i] == -1)continue;

int last = m + 1 , start = i , end;
while(i<=n && row[i] !=-1 && row[i] < last)
 {
last = row[i];
i++;
}
end = --i;
for(int f = start ; f <= end; f++)
for(int s = f ; s <= end; s++)
ans += 2*(f==s?1:2)*(m-row[f])*(row[s]-1);
}
return ans;
}

int main()
  {
for(int n,m; ~scanf("%d%d",&n,&m); )
 {
int i,j , num = n*m;
for(i = 1 ; i <= n ; i ++)
scanf("%s",field[i]+1);

vector<pair<int,int> > vt ;
vector<pair<int,int> >::iterator it , _it;
memset(row,-1,sizeof(row));
memset(col,-1,sizeof(col));
for(i = 1 ; i <= n ; i++)
for(j = 1 ; j <= m ; j++)
if(field[i][j] == 'X')
 {
row[i] = j;
col[j] = i;
vt.push_back(make_pair(i,j));
num--;
}

__int64 ans = 0;//要用长整,不然会损失精度
for(i = 1 ; i <= n; i ++)
ans += (__int64)m*m*i*(i-1);
for(j = 1 ; j <= m ; j++)
ans += (__int64)n*n*j*(j-1);
for(i = 1 ; i <= n; i++)
for(it = vt.begin() ; it != vt.end(); it++)
 {
ans -= 2*m*abs(i-it->first);
}
for(j = 1 ; j<= m; j++)
for(it = vt.begin() ; it != vt.end(); it++)
 {
ans -= 2*n*abs(j-it->second);
}
for(it = vt.begin(); it != vt.end() ; it++)
for(_it = vt.begin() ; _it != vt.end() ; _it++)
ans += abs(it->first - _it->first) + abs(it->second - _it->second);
ans += solve(n,m,row);
//交换行、列
for(i = 1 ; i <= n ; i ++)
for(j = i+1 ; j <= m ; j++)
swap(field[i][j] , field[j][i]);
ans += solve(m,n,col);

printf("%.10f\n",(double)ans/num/num);
}
return 0;
}
|
|
常用链接
随笔分类
Links
搜索
最新评论

|
|