[BZOJ 1295][SCOI 2009] 最长距离

题目大意

有一个 \(n \times m\) 的网格,每个位置是空地或障碍物。从每个空地可以到达其四连通块的空地上,若两个空地可以相互到达,则定义这两点间的距离为两个格子中心的欧几里得距离,否则没有距离。若最多可以移走 \(t\) 个障碍物,求最大的两点间距离。

\(1 \leqslant n, \; m, \; t \leqslant 30\)

题目链接

BZOJ 1295

题解

以每个点为起点跑最短路,经过障碍物时距离加 \(1\),用距离小于等于 \(t\) 的终点更新答案。

代码

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
#include <cstdio>
#include <climits>
#include <cmath>
#include <queue>
#include <algorithm>
const int MAXN = 35;
struct Node {
int dist, x, y;
bool vis;
} N[MAXN][MAXN];
int n, m, t;
int G[MAXN][MAXN];
namespace Dijkstra {
struct HeapNode {
Node *u;
int dist;
bool operator<(const HeapNode &another) const {
return dist > another.dist;
}
};
bool valid(int x, int y) {
return x <= n && x > 0 && y <= m && y > 0;
}
const int d[4][2] = {
{0, 1},
{0, -1},
{1, 0},
{-1, 0}
};
void dijkstra(Node *s) {
std::priority_queue<HeapNode> q;
s->dist = G[s->x][s->y];
q.push((HeapNode) {s, 0});
while (!q.empty()) {
Node *u = q.top().u;
q.pop();
if (u->vis) continue;
u->vis = true;
for (int i = 0; i < 4; i++) {
int x = u->x + d[i][0], y = u->y + d[i][1];
if (!valid(x, y)) continue;
Node *v = &N[x][y];
if (v->dist > u->dist + G[x][y] && u->dist + G[x][y] <= t) {
v->dist = u->dist + G[x][y];
q.push((HeapNode) {v, v->dist});
}
}
}
}
void solve(int x, int y) {
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
N[i][j].vis = false;
N[i][j].dist = INT_MAX;
}
dijkstra(&N[x][y]);
}
}
int dist(int x1, int y1, int x2, int y2) {
return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
}
int main() {
scanf("%d %d %d", &n, &m, &t);
for (int i = 1; i <= n; i++) {
static char s[MAXN];
scanf("%s", s + 1);
for (int j = 1; j <= m; j++) {
G[i][j] = s[j] - '0';
N[i][j].x = i;
N[i][j].y = j;
}
}
int ans = 0;
for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) {
Dijkstra::solve(i, j);
for (int x = 1; x <= n; x++) for (int y = 1; y <= m; y++)
if (N[x][y].dist <= t) ans = std::max(ans, dist(i, j, x, y));
}
printf("%.6lf\n", sqrt(ans));
return 0;
}