题目传送门：LOJ #546。
题意简述：
题目说的很清楚了。
题解：
将不包含起点或障碍物的连续的行或列缩成一行或一列，不会影响答案。
处理过后，新的网格图的行数和列数最多为 \(2k + 3\)。
考虑将同一行连续的不包含障碍物的格子标记为一个点，同一列同理。
这样处理过后，网格图对应的点数最多为 \(6k + 6\)。
某一行的无障碍连续段如果和某一列的无障碍连续段相交，就在它们所表示的点之间连一条权值为 \(1\) 的双向边。
从起点所在的行连续段和列连续段表示的 \(2\) 个源点开始求最短路，则给出终点的答案即为终点所在的行列连续段的距离的最小值。
因为边权为 \(1\)，所以直接 BFS 就行了。
但是这样边数是 \(\mathcal O (k^2)\) 的，考虑使用主席树优化建边即可。
边权为 \(0\) 或者 \(1\)，使用 01BFS 即可。注意不需要显式建边。
下面是代码，时间复杂度为 \(\mathcal O (k \log k)\)：
#include <cstdio>
#include <algorithm>
#include <vector>
const int Inf = 0x3f3f3f3f;
const int MK = 50005, MS = 2200005;
int N, M, K, Q, Sx, Sy, cnt;
struct dot { int x, y; } obs[MK];
inline bool cmp(dot p, dot q) { return p.x == q.x ? p.y < q.y : p.x < q.x; }
int xdx[MK * 2], xdy[MK * 2], xcx, xcy;
std::vector<int> vecx[MK * 2], idx[MK * 2], vecy[MK * 2], idy[MK * 2];
int typ[MK * 6], rc[MK * 6], lb[MK * 6], rb[MK * 6];
int pjx[MK * 2], pjy[MK * 2];
inline int gIdX(int x, int y) { return idx[x][std::lower_bound(vecx[x].begin(), vecx[x].end(), y) - vecx[x].begin()]; }
inline int gIdY(int x, int y) { return idy[y][std::lower_bound(vecy[y].begin(), vecy[y].end(), x) - vecy[y].begin()]; }
void Init() {
scanf("%d%d%d%d", &N, &M, &K, &Q);
for (int i = 1, x, y; i <= K + 1; ++i) {
scanf("%d%d", &x, &y);
if (i <= K) obs[i].x = x, obs[i].y = y;
else obs[0].x = x, obs[0].y = y;
xdx[++xcx] = x, xdy[++xcy] = y;
if (x > 1) xdx[++xcx] = x - 1;
if (y > 1) xdy[++xcy] = y - 1;
} xdx[++xcx] = N, xdy[++xcy] = M;
std::sort(xdx + 1, xdx + xcx + 1), N = xcx = std::unique(xdx + 1, xdx + xcx + 1) - xdx - 1;
std::sort(xdy + 1, xdy + xcy + 1), M = xcy = std::unique(xdy + 1, xdy + xcy + 1) - xdy - 1;
for (int i = 0; i <= K; ++i) {
obs[i].x = std::lower_bound(xdx + 1, xdx + xcx + 1, obs[i].x) - xdx;
obs[i].y = std::lower_bound(xdy + 1, xdy + xcy + 1, obs[i].y) - xdy;
} Sx = obs[0].x, Sy = obs[0].y;
std::sort(obs + 1, obs + K + 1, cmp);
for (int i = 1, x, y, p; i <= K; ++i) {
x = obs[i].x, y = obs[i].y;
p = vecx[x].empty() ? 0 : vecx[x].back();
if (y - p >= 2) {
idx[x].push_back(++cnt);
typ[cnt] = 1, rc[cnt] = x;
lb[cnt] = p + 1, rb[cnt] = y - 1;
} else idx[x].push_back(0);
p = vecy[y].empty() ? 0 : vecy[y].back();
if (x - p >= 2) {
idy[y].push_back(++cnt);
typ[cnt] = 2, rc[cnt] = y;
lb[cnt] = p + 1, rb[cnt] = x - 1;
} else idy[y].push_back(0);
vecx[x].push_back(y);
vecy[y].push_back(x);
}
for (int i = 1, p; i <= N; ++i) {
p = vecx[i].empty() ? 0 : vecx[i].back();
if (p < M) {
idx[i].push_back(++cnt);
typ[cnt] = 1, rc[cnt] = i;
lb[cnt] = p + 1, rb[cnt] = M;
} else idx[i].push_back(0);
vecx[i].push_back(M + 1);
}
for (int i = 1, p; i <= M; ++i) {
p = vecy[i].empty() ? 0 : vecy[i].back();
if (p < N) {
idy[i].push_back(++cnt);
typ[cnt] = 2, rc[cnt] = i;
lb[cnt] = p + 1, rb[cnt] = N;
} else idy[i].push_back(0);
vecy[i].push_back(N + 1);
}
}
#define mid ((l + r) >> 1)
int rtx[MK * 2], rty[MK * 2];
int rdx[MK], rdy[MK], rcx, rcy, nds;
int ls[MS], rs[MS];
std::vector<int> *id;
void Build(int &rt, int l, int r) {
if (l == r) { rt = id[l][0]; return ; }
rt = ++nds;
Build(ls[rt], l, mid), Build(rs[rt], mid + 1, r);
}
void Mdf(int &rt, int l, int r, int p, int x) {
if (l == r) { rt = x; return ; }
++nds, ls[nds] = ls[rt], rs[nds] = rs[rt], rt = nds;
if (p <= mid) Mdf(ls[rt], l, mid, p, x);
else Mdf(rs[rt], mid + 1, r, p, x);
}
void Link() {
nds = cnt;
id = idy, Build(rdx[0], 1, M);
for (int i = 1; i <= N; ++i) {
for (auto v : vecx[i]) if (v <= M) {
int id = idy[v][++pjx[v]];
if (id) Mdf(rdx[rcx + 1] = rdx[rcx], 1, M, v, id), ++rcx;
} rtx[i] = rdx[rcx];
}
id = idx, Build(rdy[0], 1, N);
for (int i = 1; i <= M; ++i) {
for (auto v : vecy[i]) if (v <= N) {
int id = idx[v][++pjy[v]];
if (id) Mdf(rdy[rcy + 1] = rdy[rcy], 1, N, v, id), ++rcy;
} rty[i] = rdy[rcy];
}
}
int vis[MS], dis[MS], que[MS * 2], ql, qr;
void Ins(int rt, int l, int r, int a, int b, int x) {
if (!rt || r < a || b < l) return ;
if (a <= l && r <= b) {
if (dis[rt] > x + 1) dis[rt] = x + 1, que[++qr] = rt;
return ;
}
Ins(ls[rt], l, mid, a, b, x);
Ins(rs[rt], mid + 1, r, a, b, x);
}
void BFS() {
for (int i = 1; i <= nds; ++i) dis[i] = Inf;
int qwqx = gIdX(Sx, Sy), qwqy = gIdY(Sx, Sy);
ql = MS + 1, qr = MS;
dis[qwqx] = dis[qwqy] = 0;
que[++qr] = qwqx, que[++qr] = qwqy;
while (ql <= qr) {
int u = que[ql++], d = dis[u];
if (vis[u]) continue;
vis[u] = 1;
if (u <= cnt) {
Ins((typ[u] == 1 ? rtx : rty)[rc[u]], 1, (typ[u] == 1 ? M : N), lb[u], rb[u], d);
} else {
if (ls[u] && dis[ls[u]] > d) dis[ls[u]] = d, que[--ql] = ls[u];
if (rs[u] && dis[rs[u]] > d) dis[rs[u]] = d, que[--ql] = rs[u];
}
}
}
int main() {
Init();
Link();
BFS();
while (Q--) {
int x, y;
scanf("%d%d", &x, &y);
x = std::lower_bound(xdx + 1, xdx + xcx + 1, x) - xdx;
y = std::lower_bound(xdy + 1, xdy + xcy + 1, y) - xdy;
int vx = gIdX(x, y), vy = gIdY(x, y);
printf("%d\n", dis[vx] == Inf ? -1 : std::min(dis[vx], dis[vy]));
}
return 0;
}