P1173 [NOI2016] 网格

___w · 2024-01-31 14:41:22 · 题解

更好的阅读体验？

P1173 [NOI2016] 网格

经典 jc 题

题意简述

有 n\times m 的矩阵，上面有 c 只跳蚤，剩下的均为蛐蛐，求至少将多少的蛐蛐替换成跳蚤使得存在两个蛐蛐它们不相通，无解输出 -1。

题目分析

注意到答案只可能为 -1,0,1,2 中的一种，因为如果存在答案 3，那么一定有一个被围在角落里的蛐蛐，只需要 2 个跳蚤。

答案 -1：蛐蛐数 <2 或者等于 2 时两只蛐蛐联通。

答案 0：所有蛐蛐不联通。

答案 1：所有蛐蛐联通且存在一个割点。

答案 2：所有蛐蛐联通且不存在一个割点。

这样我们就得到了 O(nm) 的算法。

注意到所有蛐蛐构成的图的割点有仅仅存在于跳蚤边，于是只考虑所有跳蚤的最外围一圈。但是，若选出的蛐蛐为割点，不一定为原图的割点，因为外围可能都是蛐蛐。所以我们应该取外围两圈的蛐蛐。

那么联通性问题呢？一个图不联通只能是跳蚤造成的，会造成上面选出的图中两个蛐蛐所属的联通块不联通。因此我们可以先对上面建的图进行联通块染色，在对每个跳蚤进行判断。但是单一的跳蚤可能只有一个格子与蛐蛐相邻，而这个跳蚤周围的跳蚤所形成的联通块周围的蛐蛐应该被一起考虑，所以我们应该先把所有的跳蚤分为若干个八联通的联通块（原因是斜着的跳蚤也可能分割蛐蛐，所以是一个整体），然后判断这个跳蚤联通块的周围的蛐蛐是否都处在同一个蛐蛐联通块，就可以解决联通性问题了。

代码

代码中应注意的细节：多测要清空，不要混淆变量的含义，数组应开得大一些（懒得计算了）。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define int long long
#define fi first
#define se second
#define pb push_back
#define mk make_pair
#define ll long long
#define space putchar(' ')
#define enter putchar('\n')
using namespace std;

inline int read() {
    int x = 0, f = 1;
    char c = getchar();
    while (c < '0' || c > '9') f = c == '-' ? -1 : f, c = getchar();
    while (c >= '0' && c <= '9') x = (x<<3)+(x<<1)+(c^48), c = getchar();
    return x*f;
}

inline void write(int x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) write(x/10);
    putchar('0'+x%10);
}

typedef pair <int, int> pii;
const int N = 5e6+5, P = 1000117;
const int d[8][2] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}, {1, 1}, {-1, -1}, {1, -1}, {-1, 1}};
struct edge { int to, next; } e[N*4];
int n, m, c, rt, cnt, idx, cnt_, tot, x[N], y[N], dfn[N], low[N], cut[N], isok[N], head[N];
vector <pii> pt;

struct Hash {
    int tot, a[N], tx[N], ty[N], nxt[N], head[P];
    void clear() { tot = 0, memset(head, 0, sizeof(head)); }
    void ins(int x, int y, int id) {
        int h = ((x-1)*m+y)%P;
        tx[++tot] = x, ty[tot] = y, a[tot] = id;
        nxt[tot] = head[h], head[h] = tot;
    }
    int ask(int x, int y) {
        for (int i = head[((x-1)*m+y)%P]; i; i = nxt[i]) if (tx[i] == x && ty[i] == y) return a[i];
        return 0;
    }
} h, mp, col;

void init() {
    idx = cnt = cnt_ = tot = 0;
    memset(dfn, 0, sizeof(dfn));
    memset(low, 0, sizeof(low));
    memset(cut, 0, sizeof(cut));
    memset(isok, 0, sizeof(isok));
    memset(head, 0, sizeof(head));
    pt.clear();
    h.clear(), mp.clear(), col.clear();
}

bool check() {
    rep(i, 1, n) rep(j, 1, m) if (!h.ask(i, j)) {
        rep(k, 0, 3) {
            int x = i+d[k][0], y = j+d[k][1];
            if (x < 1 || x > n || y < 1 || y > m) continue;
            if (!h.ask(x, y)) return 0;
        }
    }
    return 1;
}

void add(int x, int y) {
    e[++tot] = {y, head[x]}, head[x] = tot;
    e[++tot] = {x, head[y]}, head[y] = tot;
}

void bfs(int sx, int sy, int cl) {
    queue <pii> q; q.push(mk(sx, sy)); col.ins(sx, sy, cl);
    while (!q.empty()) {
        pii now = q.front(); q.pop();
        rep(i, 0, 3) {
            int x = now.fi+d[i][0], y = now.se+d[i][1];
            if (x < 1 || x > n || y < 1 || y > m) continue;
            if (h.ask(x, y) > 0 && !col.ask(x, y)) q.push(mk(x, y)), col.ins(x, y, cl);
        }
    }
}

bool bfs2(int sx, int sy) {
    queue <pii> q; q.push(mk(sx, sy)); mp.ins(sx, sy, -1);
    vector <pii> v;
    while (!q.empty()) {
        pii now = q.front(); q.pop();
        rep(i, 0, 7) {
            int x = now.fi+d[i][0], y = now.se+d[i][1];
            if (x < 1 || x > n || y < 1 || y > m || mp.ask(x, y)) continue;
            if (h.ask(x, y) == -1) q.push(mk(x, y)), mp.ins(x, y, -1);
            else v.pb(mk(x, y));
        }
    }
    if (v.size() <= 1) return 1;
    int tmp = col.ask(v[0].fi, v[0].se);
    for (pii x:v) if (col.ask(x.fi, x.se) != tmp) return 0;
    return 1;
}

bool pd() {
    for (pii x:pt) if (!col.ask(x.fi, x.se)) bfs(x.fi, x.se, ++idx);
    rep(i, 1, c) if (!mp.ask(x[i], y[i])) if (!bfs2(x[i], y[i])) return 1;
    return 0;
}

void tarjan(int x) {
    int flag = 0; dfn[x] = low[x] = ++cnt_;
    for (int i = head[x]; i; i = e[i].next) {
        int y = e[i].to;
        if (!dfn[y]) {
            tarjan(y);
            low[x] = min(low[x], low[y]);
            if (low[y] >= dfn[x]) {
                ++flag;
                if (x != rt || flag > 1) cut[x] = 1;
            }
        }
        else low[x] = min(low[x], dfn[y]);
    }
}

void solve() {
    init();
    n = read(), m = read(), c = read();
    rep(i, 1, c) x[i] = read(), y[i] = read(), h.ins(x[i], y[i], -1);
    if (n*m-c < 2) return write(-1), enter, void();
    if (n*m-c == 2) return write(check() ? 0 : -1), enter, void();
    rep(k, 1, c) rep(i, max(1ll, x[k]-2), min(n, x[k]+2)) rep(j, max(1ll, y[k]-2), min(m, y[k]+2)) {
        int t = h.ask(i, j);
        if (!t) {
            h.ins(i, j, ++cnt), pt.pb(mk(i, j));
            isok[cnt] = max(abs(x[k]-i), abs(y[k]-j)) <= 1;
            rep(l, 0, 3) {
                int xx = i+d[l][0], yy = j+d[l][1];
                if (xx < 1 || xx > n || yy < 1 || yy > m) continue;
                int id = h.ask(xx, yy);
                if (id > 0) add(cnt, id);
            }
        }
        else if (t > 0 && max(abs(x[k]-i), abs(y[k]-j)) <= 1) isok[t] = 1;
    }
    if (pd()) return write(0), enter, void();
    if (n == 1 || m == 1) return write(1), enter, void();
    rep (i, 1, cnt) {
        if (!dfn[i]) rt = i, tarjan(i);
        if (isok[i] && cut[i]) return write(1), enter, void();
    }
    write(2), enter;
}

signed main() {
    int t = read();
    while (t--) solve();
    return 0;
}