#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAXN = 200007, MAXH = 2007, LOG = 18;
const int DX[4] = {-1, 1, 0, 0}, DY[4] = {0, 0, -1, 1};
vector<pair<int, int>> gr[MAXN];
int h, w, p, q;
int col[MAXH][MAXH], dis[MAXH][MAXH];
int anc[LOG][MAXN], up[LOG][MAXN], dep[MAXN];
string str[MAXH];
int a[MAXN], b[MAXN];
int dsu[MAXN], sz[MAXN];
void init(int n) { for (int i = 0; i < n; ++i) dsu[i] = i, sz[i] = 1; }
int get(int i) { return (i == dsu[i] ? i : dsu[i] = get(dsu[i])); }
bool same(int i, int j) { return get(i) == get(j); }
void join(int i, int j) { i = get(i), j = get(j); if (i == j) return; if (sz[i] > sz[j]) swap(i, j); sz[i] += sz[j], dsu[j] = i; }
bool is_valid(int i, int j) { return i >= 0 && i < h && j >= 0 && j < w && str[i][j] != '#'; }
int qu_x[MAXH * MAXH], qu_y[MAXH * MAXH], fr, rr;
void add_edge(int u, int v, int w)
{
if (same(u, v)) return;
join(u, v);
gr[u].emplace_back(w, v);
gr[v].emplace_back(w, u);
}
void dfs(int u)
{
for (auto a : gr[u]) if (a.second != anc[0][u]) {
dep[a.second] = dep[u] + 1;
anc[0][a.second] = u;
up[0][a.second] = a.first;
dfs(a.second);
}
}
int max_path(int u, int v)
{
if (!same(u, v)) return -1;
int ans = 0;
if (dep[u] < dep[v]) swap(u, v);
for (int i = LOG - 1; i >= 0; --i) if (dep[u] - (1 << i) >= dep[v]) ans = max(ans, up[i][u]), u = anc[i][u];
if (u == v) return ans;
for (int i = LOG - 1; i >= 0; --i) if (anc[i][u] != anc[i][v]) ans = max(ans, max(up[i][u], up[i][v])), u = up[i][u], v = up[i][v];
return max(ans, max(up[0][u], up[0][v]));
}
int main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> h >> w >> p >> q;
for (int i = 0; i < h; ++i) cin >> str[i];
for (int i = 1; i <= p; ++i) {
cin >> a[i] >> b[i];
col[--a[i]][--b[i]] = i;
qu_x[rr] = a[i], qu_y[rr] = b[i]; ++rr;
}
init(p + 1);
while (fr < rr) {
int x = qu_x[fr], y = qu_r[fr]; ++fr;
for (int d = 0; d < 4; ++d) {
int x0 = x + DX[d], y0 = y + DY[d];
if (!is_valid(x0, y0)) continue;
if (col[x0][y0]) addEdge(col[x0][y0], col[x][y], dis[x0][y0] + dis[x][y]);
else {
col[x0][y0] = col[x][y];
dis[x0][y0] = dis[x][y] + 1;
qu_x[rr] = x0, qu_y[rr] = y0; ++rr;
}
}
}
for (int u = 1; u <= p; ++u) if (!anc[0][u]) dfs(u);
for (int lg = 1; lg < LOG; ++lg) for (int u = 1; u <= p; ++u) {
up[lg][u] = max(up[lg - 1][u], up[lg - 1][anc[lg - 1][u]]);
anc[lg][u] = anc[lg - 1][anc[lg - 1][u]];
}
for (int i = 0; i < q; ++i) {
int u, v;
cin >> u >> v;
cout << max_path(u, v) << '\n';
}
}
Compilation message
bottle.cpp: In function 'int main()':
bottle.cpp:68:31: error: 'qu_r' was not declared in this scope
int x = qu_x[fr], y = qu_r[fr]; ++fr;
^~~~
bottle.cpp:68:31: note: suggested alternative: 'qu_y'
int x = qu_x[fr], y = qu_r[fr]; ++fr;
^~~~
qu_y
bottle.cpp:72:30: error: 'addEdge' was not declared in this scope
if (col[x0][y0]) addEdge(col[x0][y0], col[x][y], dis[x0][y0] + dis[x][y]);
^~~~~~~
bottle.cpp:72:30: note: suggested alternative: 'add_edge'
if (col[x0][y0]) addEdge(col[x0][y0], col[x][y], dis[x0][y0] + dis[x][y]);
^~~~~~~
add_edge
