「LOJ 2084」「NOI2016」网格

发表于

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

他们在一个 nn 行 mm 列的网格上排兵布阵。其中的 cc 个格子中 (0≤c≤nm)(0 \leq c \leq nm) ，每个格子有一只蛐蛐，其余的格子中，每个格子有一只跳蚤。

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

现在，蛐蛐国王希望，将某些（零个，一个或多个）跳蚤替换成蛐蛐，使得在此之后存在至少两只跳蚤不连通。你需要首先判断蛐蛐国王的希望能否被达成。如果能够达成，你还需要最小化被替换的跳蚤的个数。

Constraints

1≤n,m≤1091 \leq n,m \leq 10^9 ， ∑c≤105\sum c \leq 10^5 ， 1≤T≤201 \leq T \leq 20

Solution

观察可得：答案为 −1,0,1,2-1,0,1,2 。分情况讨论如下：

1.1. 当跳蚤数量 ≤1\leq 1 或跳蚤数量为 22 且只有一个连通块时，答案为 −1-1 。

2.2. 存在至少两个连通块时，答案为 00 。

3.3. 连通块个数为 11 但存在割点时，答案为 11 。

4.4. 其他情况答案为 22 。

主要过程在离散化建图。需要提取出每只蛐蛐周围的八个点，然后判断这些点里每只跳蚤向右和向下的最近的一个点，若是跳蚤则连上一条边。需要手动多围上一圈边界。

跑 tarjan 求割点即可。记得判断 n=1n=1 和 m=1m=1 的特殊情况。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<cstdio>
#include<algorithm> 
#include<cstring>
#define LL long long
using namespace std;
const int N=1e5+5;
int T,n,m,C,tot,cnt,cntx,cnty,cntb;
int up,dn,le,ri,tim;
int X[N*3],Y[N*3];
int first[N*25],low[N*25],dfn[N*25];
bool mode,havecut;
struct edge{int to,next;}e[N*100];
struct node
{
	int id,x,y;
	bool operator < (const node& a) const
	{
		if(mode)
			if(x==a.x)return y<a.y;
			else return x<a.x;
		else
			if(y==a.y)return x<a.x;
			else return y<a.y;
	}
	bool operator == (const node& a) const
	{
		return x==a.x&&y==a.y;
	}
}a[N],b[N*25];
int read()
{
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
	return x*f;
}
void ins(int u,int v)
{
	e[++tot]=(edge){v,first[u]};first[u]=tot;
	e[++tot]=(edge){u,first[v]};first[v]=tot;
}
void tarjan(int x,int fa)
{
	dfn[x]=low[x]=++tim;int son=0;
	for(int i=first[x];i;i=e[i].next)
	{
		int to=e[i].to;
		if(to==fa)continue;
		if(!dfn[to])
		{
			son++;tarjan(to,x);
			low[x]=min(low[x],low[to]);
			if(dfn[x]<=low[to]&&(fa!=-1||(fa==-1&&son>=2)))havecut=true;
		}
		else low[x]=min(low[x],low[to]);
	}
}
void work()
{
	n=read();m=read();C=read();
	cnt=cntx=cnty=cntb=tot=tim=0;havecut=false;
	for(int x,y,i=1;i<=C;i++)
	{
		x=read();y=read();a[i]=(node){0,x,y};
		X[++cntx]=x;Y[++cnty]=y;
		if(x>1)X[++cntx]=x-1,b[++cntb]=(node){0,x-1,y};
		if(x<n)X[++cntx]=x+1,b[++cntb]=(node){0,x+1,y};
		if(y>1)Y[++cnty]=y-1,b[++cntb]=(node){0,x,y-1};
		if(y<m)Y[++cnty]=y+1,b[++cntb]=(node){0,x,y+1};
		if(x>1&&y>1)b[++cntb]=(node){0,x-1,y-1};
		if(x>1&&y<m)b[++cntb]=(node){0,x-1,y+1};
		if(x<n&&y>1)b[++cntb]=(node){0,x+1,y-1};
		if(x<n&&y<m)b[++cntb]=(node){0,x+1,y+1};
	}
	if(1ll*n*m-C<=1){printf("-1\n");return;}
	le=n+1;up=m+1;ri=dn=0;
	memset(dfn,0,sizeof(dfn));
	memset(low,0,sizeof(low));
	memset(first,0,sizeof(first));
	for(int i=1;i<=cntx;i++)le=min(le,X[i]),ri=max(ri,X[i]);
	for(int i=1;i<=cnty;i++)up=min(up,Y[i]),dn=max(dn,Y[i]);
	if(le>1)le--;if(up>1)up--;
	if(ri<n)ri++;if(dn<m)dn++;
	X[++cntx]=le;X[++cntx]=ri;
	Y[++cnty]=up;Y[++cnty]=dn;
	sort(X+1,X+cntx+1);
	cntx=unique(X+1,X+cntx+1)-X-1;
	sort(Y+1,Y+cnty+1);
	cnty=unique(Y+1,Y+cnty+1)-Y-1;
	for(int i=1;i<=cntx;i++)
		b[++cntb]=(node){0,X[i],Y[1]},b[++cntb]=(node){0,X[i],Y[cnty]};
	for(int i=1;i<=cnty;i++)
		b[++cntb]=(node){0,X[1],Y[i]},b[++cntb]=(node){0,X[cntx],Y[i]};
	mode=false;sort(a+1,a+C+1);sort(b+1,b+cntb+1);
	cntb=unique(b+1,b+cntb+1)-b-1;
	for(int i=1;i<=C;i++)
		a[i].x=lower_bound(X+1,X+cntx+1,a[i].x)-X,
		a[i].y=lower_bound(Y+1,Y+cnty+1,a[i].y)-Y;
	for(int i=1;i<=cntb;i++)
		b[i].x=lower_bound(X+1,X+cntx+1,b[i].x)-X,
		b[i].y=lower_bound(Y+1,Y+cnty+1,b[i].y)-Y,
		b[i].id=i;
	for(int ta=1,tb=1,i=1;i<=cntb;i++)
	{
		node tmp=b[i];
		while(ta<=C&&a[ta]<tmp)ta++;
		if(ta>=1&&ta<=C&&a[ta]==tmp)continue;
		cnt++;tmp.x++;
		while(ta<=C&&a[ta]<tmp)ta++;
		while(tb<=cntb&&b[tb]<tmp)tb++;
		if(ta>=1&&ta<=C&&a[ta]==tmp)continue;
		if(tb>=1&&tb<=cntb&&b[tb].y==b[i].y)ins(b[i].id,b[tb].id);
	}
	mode=true;sort(a+1,a+C+1);sort(b+1,b+cntb+1);
	for(int ta=1,tb=1,i=1;i<=cntb;i++)
	{
		node tmp=b[i];
		while(ta<=C&&a[ta]<tmp)ta++;
		if(ta>=1&&ta<=C&&a[ta]==tmp)continue;
		tmp.y++;
		while(ta<=C&&a[ta]<tmp)ta++;
		while(tb<=cntb&&b[tb]<tmp)tb++;
		if(ta>=1&&ta<=C&&a[ta]==tmp)continue;
		if(tb>=1&&tb<=cntb&&b[tb].x==b[i].x)ins(b[i].id,b[tb].id);
	}
	if(tot)tarjan(e[1].to,-1);
	if(tim<cnt)printf("0\n");
	else
	{
		if(1ll*n*m-C==2)printf("-1\n");
		else if(n==1||m==1)printf("1\n");
		else if(havecut)printf("1\n");
		else printf("2\n");
	}
}
int main()
{
	T=read();while(T--)work();
	return 0;
}