[NOI2016] 网格

大家吼啊！

早上好！本猫妖又来了！

一道较难的题，花了好久才做对/(ㄒoㄒ)/~~

惨的要死

之前全都是

后面才

全AC

爽！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

代码奉上

#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;
}

求三连！还差一粉即可200粉！