DDOSvoid's Blog

The 14th Chinese Northeast Collegiate Programming Contest L PepperLa's Express

发表于 分类于
本文字数： 2.6k 阅读时长 ≈ 2 分钟

题目描述

https://codeforces.com/gym/102801/problem/L

简要题意：给定一个 $n\times m\times k$ 的六连通三维空间，在这个三维空间的整点上有一些点是居民的住房，另有一些点是邮局，其他点都是空地，现在要求选一块空地改造成邮局，定义一个居民到邮局的距离为到离他最近的邮局的距离他，求如何选择空地改造成邮局可以使所有居民到邮局的距离的最大值最小

$n,m,k\le 100$

Solution

首先跑一个多源 $bfs$，可以得到每个居民住房到邮局的距离

然后我们考虑二分答案 $x$，那么问题等价于是否存在一个空地，他到某些住房的距离的最大值小于等于 $x$

注意到三维曼哈顿距离没法转换成切比雪夫距离（至少我不会），但是我们同时注意到总点数小于等于 $1e6$，那么我们尝试枚举所有空地，一个点到一堆点的 $k$ 维曼哈顿距离的最大值是一个经典问题，我们只需要枚举符号即可

时间复杂度为 $O(2^3nmk)$

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
#include <iostream>
#include <queue>
#include <tuple>
#include <algorithm>
#include <vector>
#define maxn 110
#define INF 1000000000
#define ll long long
using namespace std;

int dx[] = { 1, -1, 0, 0, 0, 0 };
int dy[] = { 0, 0, 1, -1, 0, 0 };
int dz[] = { 0, 0, 0, 0, 1, -1 };

int n, m, k, a[maxn][maxn][maxn];
char s[maxn];

int dis[maxn][maxn][maxn]; bool vis[maxn][maxn][maxn];
void bfs() {
    queue<tuple<int, int, int>> Q;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            for (int k = 1; k <= ::k; ++k) {
                vis[i][j][k] = 0; 
                dis[i][j][k] = a[i][j][k] > 0 ? 0 : INF;
                if (a[i][j][k] > 0) Q.push({ i, j, k }), vis[i][j][k] = 1; 
            }
    while (!Q.empty()) {
        int i, j, k; tie(i, j, k) = Q.front(); Q.pop();
        for (int d = 0; d < 6; ++d) {
            int x = i + dx[d], y = j + dy[d], z = k + dz[d];
            if (x < 1 || x > n || y < 1 || y > m || z < 1 || z > ::k) continue;
            if (vis[x][y][z]) continue; vis[x][y][z] = 1; 
            dis[x][y][z] = dis[i][j][k] + 1; Q.push({ x, y, z });
        }
    }
}

int d[8];
bool check(int x) {
    for (int S = 0; S < 8; ++S) d[S] = -INF;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            for (int k = 1; k <= ::k; ++k) { 
                if (~a[i][j][k] || dis[i][j][k] <= x) continue;
                for (int S = 0; S < 8; ++S) {
                    int res = 0;
                    res += (S & 1) ? i : -i;
                    res += (S & 2) ? j : -j;
                    res += (S & 4) ? k : -k;
                    d[S] = max(d[S], res);
                }
            }
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            for (int k = 1; k <= ::k; ++k) { 
                if (a[i][j][k] == -1) continue;
                int mx = -INF;
                for (int S = 0; S < 8; ++S) {
                    int res = 0;
                    res += (S & 1) ? i : -i;
                    res += (S & 2) ? j : -j;
                    res += (S & 4) ? k : -k;
                    mx = max(mx, res + d[S ^ 7]);
                } if (mx <= x) return 1; 
            }
    return 0;
}

void work() {
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            cin >> s + 1;
            for (int k = 1; k <= ::k; ++k)
                if (s[k] == '*') a[i][j][k] = -1;
                else if (s[k] == '@') a[i][j][k] = 1;
                else a[i][j][k] = 0; 
        }
    bfs(); 
    int l = 0, r = INF, mid, ans;
    while (l <= r) {
        mid = l + r >> 1;
        if (check(mid)) ans = mid, r = mid - 1; 
        else l = mid + 1; 
    } cout << ans << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    while (cin >> n >> m >> k) work(); 
    return 0;
}