[SCOI 2009] 最长距离

发表于2017-05-02更新于2020-08-06

题目大意

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

1⩽n,  m,  t⩽301 \leqslant n, \; m, \; t \leqslant 30

题目链接

【SCOI 2009】最长距离 - Luogu 4162

题解

以每个点为起点跑最短路，经过障碍物时距离加 11，用距离小于等于 tt 的终点更新答案。

代码

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;
}