HDU 5725 Game【思维，细节】

ACM_思维

题目链接：

http://acm.split.hdu.edu.cn/showproblem.php?pid=5725

题意：

给定$n*m$的矩阵及守卫的位置， 守卫可以攻击周围$8$个方向的其他守卫。已知初始位置守卫之间不存在攻击，求所有点（除守卫）之间不经过守卫的最短路之和。

分析:

最初想简单了以为只有同行同列的才会被阻隔= = 还想这不傻逼题么，写完发现自己是才是傻逼T^T
先来分析一下：

  1. 可以将所求转化为所有合法点对间的最短路径的平均值，即有合法最短点对的最短路径之和，再除以合法点对个数。
  2. 除了两个均为守卫外，任意两点可达，可能路径均被守卫阻隔(被阻隔要绕道走)， 可能存在无守卫的路径(直达，无需绕路)。

  3. 不被阻隔的两点最短路即为曼哈顿距离，被阻隔的两点由于守卫分布的限制有一个很重要的性质，

    任意两点间的最短路径只会至多被一个Guard所干扰

    所以这种情况下要多走两格。

  4. 被阻隔一共有两种情况：守卫同行同列分布和呈阶梯型分布

所以我们先对没有阻隔的点求个曼哈顿距离和，再对守卫的分布分类讨论一下，分为从左到右，从上到下，上升和下降阶梯分布。注意！上升下降情况下，同行同列不要算重！
虽然整体思路很显然，但是细节的处理还是要注意！

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/*************************************************************************
    > File Name: 5725.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/8/25 13:57:24
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
#define mem(a, b) memset(a, b, sizeof(a))
typedef long long ll;
const int maxn = 1e3 + 5;
char s[maxn];
int x[maxn];
int y[maxn];
int cntx[maxn];
int cnty[maxn];
int main (void)
{
	int T;scanf("%d", &T);
	while(T--){
		ll tot = 0;
		mem(x, -1);mem(cntx, 0);
		mem(y, -1);mem(cnty, 0);
		int n, m;scanf("%d%d", &n, &m);
		getchar();
		for(int i = 0; i < n; i++){
			gets(s);
			for(int j = 0; j < m; j++){
				if(s[j] == 'G'){
					y[i] = j; x[j] = i;
				}else{
					cntx[i]++;cnty[j]++;
					tot++;
				}
			}
		}
		ll ans = 0;
		for(int i = 0; i < n; i++){
			for(int j = i + 1; j < n; j++){
				ans += (j - i) * cntx[i] * cntx[j];
			}
		}
		for(int i = 0; i < m; i++){
			for(int j = i + 1; j < m; j++){
				ans += (j - i) * cnty[i] * cnty[j];
			}
		}
		ans *= 2;
		//cout<<ans<<' '<<tot<<endl;
		//左右，下降
		int cnt = 0;
		for(int i = 0; i < n; i++){
			if(y[i] > y[i - 1]) cnt += y[i];
			else if(y[i] == -1) cnt = 0;
			else cnt = y[i];
			ans += cnt * 4ll * (m - y[i] - 1);
		}
		//上下， 上升
		cnt = 0;
		for(int i = 0; i < m; i++){
			if(x[i] > x[i - 1]) cnt += x[i];
			else if(x[i] == -1) cnt = 0;
			else cnt = x[i];
			ans += cnt * 4ll * (n - x[i] - 1);
		}
		//左右，上升
		cnt = 0;
		for(int i = n - 1; i >= 0; i--){
			if(y[i + 1] > y[i])	cnt = 0;
			ans += cnt * 4ll * (m - y[i] - 1);
			if(y[i] > y[i + 1]) cnt += y[i];
			else if(y[i] == -1) cnt = 0;
			else cnt = y[i];
		}	
		//上下， 下降
		cnt = 0;
		for(int i = m - 1; i >= 0; i--){
			if(x[i + 1] > x[i])	cnt = 0;
			ans += cnt * 4ll * (n - x[i] - 1);
			if(x[i] > x[i + 1]) cnt += x[i];
			else if(x[i] == -1) cnt = 0;
			else cnt = x[i];
		}
		printf("%.4f\n", 1.0 * ans /(double)(tot * tot));
	}
	return 0;
}
文章目录
  1. 1. 题目链接：
  2. 2. 题意：
  3. 3. 分析:
  4. 4. 代码：