Description

跳蚤国王和蛐蛐国王在玩一个游戏。

他们在一个 $n$行 $m$列的网格上排兵布阵。其中的 $c$个格子中 ($0≤c≤nm$),每个格子有一只蛐蛐,其余的格子中,每个格子有一只跳蚤。

我们称占据的格子有公共边的两只跳蚤是相邻的。我们称两只跳蚤是连通的,当且仅当这两只跳蚤相邻,或存在另一只跳蚤与这两只跳蚤都连通。

现在,蛐蛐国王希望,将某些(0 个,1 个或多个)跳蚤替换成蛐蛐,使得在此之后存在至少两只跳蚤不连通。

Input

每个输入文件包含多组数据。

输入文件的第一行只有一个整数 $T$,表示数据的组数。保证 $1≤T≤20$。

接下来依次输入 $T$ 组数据,每组数据的第一行包含三个整数 $n, m, c, 1≤n,m≤10^9, 0≤c≤nm, \sum c \le 10^5$.

接下来 $c$ 行,每行包含两个整数 $x, y$,表示第 $x$ 行,第 $y$ 列的格子被一个蛐蛐占据($1≤x≤n,1≤y≤m$)。每一组数据当中,同一个蛐蛐不会被多次描述。

同一行相邻的整数之间由一个空格隔开。

Output

对于每一组数据依次输出一行答案。

如果这组数据中,蛐蛐国王的希望不能被达成,输出”-1”。否则,输出被替换的跳蚤的个数的最小值。

Solution

容易发现答案只可能为-1, 0, 1, 2。

答案为-1时,要么不足两个空位,要么只有两个空位且连在一起。

答案为0时,即跳蚤一开始就不连通。我们可以将八连通的蛐蛐视作一个连通块,考虑与一个连通块内的一个或几个蛐蛐八连通的所有跳蚤,若这些跳蚤不为四连通,则说明答案为0。

接下来答案最多为2,我们只需判断答案是否为1即可。考虑将原图中的跳蚤按四连通建图,则答案为1当且仅当这个图中有割点,这样就能拿到60分。

当$n, m$很大时,我们发现这张图中的很多点都没有作用。事实上,我们只需要保留以所有蛐蛐为中心的一个$5 \times 5$区域内的所有跳蚤就行了。需要注意的是此时如果一个点在所有包含它的$5 \times 5$区域中都是外层点,且这个点被作为割点,那么它并不是原图的割点。另外在$n = 1$或$m = 1$时也会有特殊情况,需要特判。

时间复杂度$O(25\sum c)$

Source

#include <cstdio>
#include <algorithm>
#include <cstring>

#define For(i, j, k) for(int i = j; i <= k; i++)
#define Set(i, v) memset(i, v, sizeof i)

using namespace std;

const int N = 2500010, M = N * 4;
const int dx[4] = {1, -1, 0, 0}, dy[4] = {0, 0, 1, -1};

int n, m, c;
int Begin[N], Next[M], to[M], e;

void Adde(int u, int v){
	to[++e] = v;
	Next[e] = Begin[u];
	Begin[u] = e;
	if(e & 1) Adde(v, u);
}

struct Point{
	int x, y, id;

	Point(int _x = 0, int _y = 0, int _id = 0):x(_x), y(_y), id(_id){}
}P[N];

int cv, cp;

void Addv(int x, int y){
	if(x <= 0 || y <= 0 || x > n || y > m) return;
	++cv;
	P[cv] = Point(x, y, cv);
}

bool cmp1(const Point &A, const Point &B){
	return A.x != B.x ? A.x < B.x : (A.y != B.y ? A.y < B.y : A.id < B.id);
}

bool cmp2(const Point &A, const Point &B){
	return A.y != B.y ? A.y < B.y : A.x < B.x;
}

bool vis[N];
int cn, inner;

void DFS(int h){
	vis[h] = true;
	if(h > c) ++cn;
	for(int i = Begin[h]; i; i = Next[i]){
		int u = to[i];
		if(!vis[u]) DFS(u);
	}
}

int low[N], pre[N], dfn;
bool flag;

void Tarjan(int h, int fa = 0){
	low[h] = pre[h] = ++dfn;
	int ch = 0;
	for(int i = Begin[h]; i; i = Next[i]){
		int u = to[i];
		if(u <= c || u == fa) continue;
		if(pre[u]) low[h] = min(low[h], pre[u]);
		else{
			++ch;
			Tarjan(u, h);
			low[h] = min(low[h], low[u]);
			if(pre[h] > 1 && low[u] >= pre[h] && h <= inner) flag = true;
		}
	}
	if(pre[h] == 1 && ch > 1 && h <= inner) flag = true;
}

int solve(){
	if(c > 1LL * n * m - 2) return -1;
	if(c == 1LL * n * m - 2){
		For(i, 1, (n + 1) * m) vis[i] = 0;
		For(i, 1, c) vis[P[i].x * m + P[i].y] = true;
		For(i, m + 1, (n + 1) * m) if(!vis[i]) P[++cp] = Point((i - 1) / m, (i - 1) % m + 1, 0);
		For(i, 0, 3) if(P[cp - 1].x + dx[i] == P[cp].x && P[cp - 1].y + dy[i] == P[cp].y) return -1;
		return 0;
	}
	if(c == 0){
		if(n == 1 || m == 1) return 1;
		return 2;
	}
	sort(P + 1, P + cv + 1, cmp1);
	For(i, 1, cv) if(P[i].x != P[i - 1].x || P[i].y != P[i - 1].y) P[++cp] = P[i];
	For(i, 1, cp - 1) if(P[i + 1].x == P[i].x && P[i + 1].y == P[i].y + 1) Adde(P[i].id, P[i + 1].id);
	sort(P + 1, P + cp + 1, cmp2);
	For(i, 1, cp - 1) if(P[i + 1].y == P[i].y && P[i + 1].x == P[i].x + 1) Adde(P[i].id, P[i + 1].id);
	flag = false;
	For(i, 1, cp){
		int j = P[i].id;
		if(vis[j] || j <= c) continue;
		cn = dfn = 0;
		DFS(j), Tarjan(j);
		if(cn != dfn) return 0;
	}
	if(n == 1 || m == 1) return 1;
	return flag ? 1 : 2;
}

int main(){
	int T;
	scanf("%d", &T);
	while(T--){
		scanf("%d%d%d", &n, &m, &c);
		e = cp = 0, cv = c;
		For(i, 1, c){
			int x, y;
			scanf("%d%d", &x, &y);
			P[i] = Point(x, y, i);
		}
		For(i, 1, c) For(u, -1, 1) For(v, -1, 1) if(u || v) Addv(P[i].x + u, P[i].y + v);
		inner = cv;
		For(i, 1, c) For(u, -2, 2) For(v, -2, 2) if(abs(u) > 1 || abs(v) > 1) Addv(P[i].x + u, P[i].y + v);
		For(i, 0, cv) Begin[i] = pre[i] = vis[i] = 0;
		printf("%d\n", solve());
	}
	return 0;
}