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
| #include<bits/stdc++.h>
using namespace std;
int dis[210][200010];
int dis_pos[210];
int bk[45];
int c[200010];
int xp[4] = { 0, 0, -1, 1 }, yp[4] = { -1, 1, 0 , 0 };
int n, m, k, q;
int tot = 0;
int pos(int x, int y) {
return (x - 1) * m + y;
}
pair<int, int> apos(int p) {
return make_pair((p - 1) / m + 1, (p - 1) % m + 1);
}
int check(int x, int y) {
if (x >= 1 && x <= n && y >= 1 && y <= m)return 1;
return 0;
}
int mp[200010];
void bfs(int num, int x, int y) {
c[pos(x, y)] = 1;
queue<int>q;
dis[num][pos(x, y)] = 0;
q.push(pos(x, y));
while (!q.empty()) {
int top1 = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
auto p = apos(top1);
p.first += xp[i], p.second += yp[i];
if (!check(p.first, p.second))continue;
if (c[pos(p.first, p.second)])continue;
if (mp[pos(p.first, p.second)])continue;
c[pos(p.first, p.second)] = 1;
dis[num][pos(p.first, p.second)] = dis[num][top1] + 1;
q.push(pos(p.first, p.second));
}
}
}
signed main() {
memset(dis, -1, sizeof(dis));
scanf("%d%d%d%d", &n, &m, &k, &q);
for (int i = 1; i <= k; i++) {
int x, y;
scanf("%d%d", &x, &y);
bk[i] = pos(x, y);
mp[pos(x, y)] = 1;
}
for (int i = 1; i <= k; i++) {
int x = apos(bk[i]).first, y = apos(bk[i]).second;
for (int j = 0; j < 4; j++) {
int xn = x + xp[j], yn = y + yp[j];
if (!check(xn, yn))continue;
if (mp[pos(xn, yn)])continue;
dis_pos[++tot] = pos(xn, yn);
memset(c, 0, sizeof(c));
bfs(tot, xn, yn);
}
}
while (q--) {
int xl, yl, xr, yr;
scanf("%d%d%d%d", &xl, &yl, &xr, &yr);
if (mp[pos(xl, yl)] || mp[pos(xr, yr)]) {
printf("-1\n");
continue;
}
int ff = 0;
for (int i = 1; i <= k; i++) {
auto p = apos(bk[i]);
if (p.first >= min(xl, xr) && p.first <= max(xl, xr) && p.second >= min(yl, yr) && p.second <= max(yl, yr)) {
ff = 1;
break;
}
}
if (!ff) {
printf("%d\n", abs(xl - xr) + abs(yl - yr));
continue;
}
int mmin = 1e9;
for (int i = 1; i <= tot; i++) {
if (dis[i][pos(xl, yl)] == -1 || dis[i][pos(xr, yr)] == -1)continue;
mmin = min(mmin, dis[i][pos(xl, yl)] + dis[i][pos(xr, yr)]);
}
if (mmin == 1e9)printf("-1\n");
else printf("%d\n", mmin);
}
return 0;
}
|