LOJ 546. 「LibreOJ β Round #7」网格图

题目传送门：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;
}

LOJ 546. 「LibreOJ β Round #7」网格图

原文：https://www.cnblogs.com/PinkRabbit/p/LOJ546.html