DDOSvoid's Blog

2020 China Collegiate Programming Contest, Weihai Site B.Labyrinth

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

题目描述

https://codeforces.com/gym/102798/problem/B

简要题意：给定一个 $n\times m$ 的四连通网格图，现在有 $k$ 个点不能走，另外还有 $q$ 次询问，每次询问给定起点 $(sx,sy)$ 和中终点 $(tx,ty)$，求起点到终点的最短路

$n\times m \le 2\times 10^5,k\le 42,q\le 10^5$

Solution

我们考虑如果两个点之间有不能走的点，那么一定存在最短路是沿着不能走的点的

注意到 $k$ 很小，所以我们把 $k$ 周围的点都拿出来然后做多源 $bfs$

最后枚举最短路是经过的那个点即可

时间复杂度 $O(knm+kq)$

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
#include <iostream>
#include <cstdio>
#include <queue>
#include <tuple>
#define maxn 200010
#define maxm 170
#define INF 1000000000
using namespace std;

int n, m, k, q;

int u[maxm], v[maxm];

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

inline int id(int x, int y) { return (x - 1) * m + y; }

int dis[maxn][maxm], cnt; bool vis[maxn], use[maxn];
void bfs(int k, int x, int y) {
    queue<pair<int, int>> Q; Q.push({ x, y });
    dis[id(x, y)][k] = 0;
    fill(vis, vis + maxn, 0); vis[id(x, y)] = 1; 
    while (!Q.empty()) {
        int sx, sy; tie(sx, sy) = Q.front(); Q.pop();
        for (int i = 0; i < 4; ++i) {
            int tx = sx + dx[i], ty = sy + dy[i];
            if (tx < 1 || tx > n || ty < 1 || ty > m || vis[id(tx, ty)] || use[id(tx, ty)]) continue;
            dis[id(tx, ty)][k] = dis[id(sx, sy)][k] + 1;
            Q.push({ tx, ty }); vis[id(tx, ty)] = 1; 
        }
    }
} 


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

    cin >> n >> m >> k >> q; fill(dis[0], dis[0] + maxn * maxm, INF);
    for (int i = 1; i <= k; ++i) cin >> u[i] >> v[i], use[id(u[i], v[i])] = 1;
    for (int i = 1; i <= k; ++i) 
        for (int j = 0; j < 4; ++j) {
            int x = u[i] + dx[j], y = v[i] + dy[j];
            if (x < 1 || x > n || y < 1 || y > m || use[id(x, y)]) continue;
            bfs(++cnt, x, y); 
        }
    for (int i = 1; i <= q; ++i) {
        int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty;
        bool F = 1;
        for (int j = 1; j <= k; ++j)
            if (min(sx, tx) <= u[j] && u[j] <= max(sx, tx) && min(sy, ty) <= v[j] && v[j] <= max(sy, ty)) F = 0;
        if (F) { cout << abs(tx - sx) + abs(ty - sy) << "\n"; continue; }
        int ans = INF;
        for (int j = 1; j <= cnt; ++j) ans = min(ans, dis[id(sx, sy)][j] + dis[id(tx, ty)][j]);
        ans == INF ? cout << "-1\n" : cout << ans << "\n"; 
    } 
    return 0;
}