/**//* 题意: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 3X. 1的左边到1、2、3的右边需要多加2 2的左边到2、3的右边也需要多加2 另外,对于下图: 1..X.. 2X. 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
搜索
最新评论
|
|