列表

详情

NC17896. [NOI2016]网格

描述

跳蚤国王和蛐蛐国王在玩一个游戏。
他们在一个 n 行 m 列的网格上排兵布阵。其中的 c 个格子中 (0≤c≤nm)，每个格子有一只蛐蛐，其余的格子中，每个格子有一只跳蚤。
我们称占据的格子有公共边的两只跳蚤是相邻的。
我们称两只跳蚤是连通的，当且仅当这两只跳蚤相邻，或存在另一只跳蚤与这两只跳蚤都连通。
现在，蛐蛐国王希望，将某些（0 个，1 个或多个）跳蚤替换成蛐蛐，使得在此之后存在至少两只跳蚤不连通。
例如：我们用图表示一只跳蚤，用图表示一只蛐蛐，那么图 1 描述了一个 n=4,m=4,c=2的情况。
这种情况下蛐蛐国王可以通过将第 2 行第 2 列，和第 3 行第 3 列的两只跳蚤替换为蛐蛐，从而达成他的希望，如图 2 所示。并且，不存在更优的方案，但是可能存在其他替换 2 只跳蚤的方案。
你需要首先判断蛐蛐国王的希望能否被达成。如果能够达成，你还需要最小化被替换的跳蚤的个数。

输入描述

每个输入文件包含多组数据。
输入文件的第一行只有一个整数 T，表示数据的组数。保证 1≤T≤20。
接下来依次输入 TT 组数据，每组数据的第一行包含三个整数 n, m, c。
保证1≤n,m≤10^9,0≤c≤min(nm,105)
接下来 c行，每行包含两个整数 x, y表示第 x 行，第 y 列的格子被一个蛐蛐占据（1≤x≤n,1≤y≤m）每一组数据当中，同一个蛐蛐不会被多次描述。
同一行相邻的整数之间由一个空格隔开。
1≤n,m≤10^9, 0≤c≤nm, 1≤x≤n, 1≤y≤m
1≤T≤20。我们记 ∑c为某个测试点中，其 T 组输入数据的所有 c 的总和,∑c≤10^5

输出描述

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

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

示例1

输入: 

4
4 4 2
1 1
4 4
2 3 1
1 2
2 2 2
1 1
2 2
1 1 0

输出: 

2
1
0
-1

说明:

第一组数据就是问题描述中的例子。
对于第二组数据，可以将第 2 行第 2 列的一只跳蚤替换为蛐蛐，从而使得存在两只跳蚤不连通
并且不存在更优的方案。
对于第三组数据，最初已经存在两只跳蚤不连通，故不需要再进行替换。
对于第四组数据，由于最多只有一只跳蚤，所以无论如何替换都不能存在两只跳蚤不连通

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++11(clang++ 3.9) 解法, 执行用时: 514ms, 内存消耗: 54352K, 提交时间: 2020-03-08 15:01:58 

#include<map>
#include<cmath>
#include<stack>
#include<queue>
#include<cstdio>
#include<cctype>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef double dl;
const int INF=2e9;
const int N=1e5+5;
const int M=N*24;
const int P=666233;
const int B=1e9+7;
inline int read()
{
	int X=0,w=0;
	char ch=0;
	while(!isdigit(ch))
	{
		w|=ch=='-';
		ch=getchar();
	}
	while(isdigit(ch))
	X=(X<<3)+(X<<1)+(ch^48),ch=getchar();
	return w?-X:X;
}
struct Hash
{
	int cnt,head[P],nxt[M];
	ll to[M];
	inline void init()
	{
		cnt=0;
		memset(head,0,sizeof(head));
	}
	inline void add(ll x,ll y)
	{
		ll v=(x*B+y);
		int u=v%P;
		to[++cnt]=v;
		nxt[cnt]=head[u];
		head[u]=cnt;
	}
	inline int qry(ll x,ll y)
	{
		ll v=(x*B+y);
		int u=v%P;
		for(int i=head[u];i;i=nxt[i])
		if(to[i]==v) return i;
		return 0;
	}
}mp1,mp2;
struct node
{
	int x,y;
}p[N],q[M];
int im[M],n,m,c;
int DX[4]={1,0,-1,0};
int DY[4]={0,1,0,-1};
int dx[24]={-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2};
int dy[24]={-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2};
inline dl dis(dl x1,dl y1,dl x2,dl y2)
{
	dl x=x1-x2,y=y1-y2;
	return sqrt(x*x+y*y);
}
struct edge
{
	int to,nxt;
}e[M*4];
int cnt,head[M],dfn[M],low[M],to[M],id,t,rtson;
bool cut[M];
inline void add(int u,int v)
{
	e[++cnt].to=v;
	e[cnt].nxt=head[u];
	head[u]=cnt;
}
void tarjan(int u,int f)
{
	to[u]=id;
	dfn[u]=low[u]=++t;
	for(int i=head[u];i;i=e[i].nxt)
	{
		int v=e[i].to;
		if(!dfn[v])
		{
			tarjan(v,u);
			low[u]=min(low[u],low[v]);
			if(low[v]>=dfn[u]&&f) cut[u]=1;
			if(!f) rtson++;
		}
		else if(f!=v)
		low[u]=min(low[u],dfn[v]);
	}
	if(!f&&rtson>=2) cut[u]=1;
}
bool vis1[M],vis2[M];
int dui[M],top;
inline void init()
{
	for(int i=1;i<=mp1.cnt;i++) vis2[i]=0;
	for(int i=1;i<=mp2.cnt;i++) cut[i]=head[i]=low[i]=dfn[i]=to[i]=vis1[i]=0;
	mp1.init();
	mp2.init();
	t=cnt=0;
}
inline void getnode(int x,int y,int iid)
{
	vis2[iid]=1;
	for(int i=0;i<4;i++)
	{
		int nx=x+DX[i],ny=y+DY[i];
		if(nx<1||nx>n||ny<1||ny>m) continue;
		int nxtid=mp1.qry(nx,ny);
		if(nxtid) continue;
		int tmp=mp2.qry(nx,ny);
		if(vis1[tmp]) continue;
		vis1[tmp]=1;
		dui[++top]=tmp;
		
	}
	for(int i=0;i<4;i++)
	{
		int nx=x+DX[i],ny=y+DY[i];
		if(nx<1||nx>n||ny<1||ny>m) continue;
		int nxtid=mp1.qry(nx,ny);
		if(nxtid)
		{
			if(!vis2[nxtid]) getnode(nx,ny,nxtid);
			continue; 
		}
	}
	for(int i=0;i<4;i++)
	{
		int nx=x+DX[i],ny=y+DY[i];
		if(nx<1||nx>n||ny<1||ny>m) continue;
		vis1[mp2.qry(nx,ny)]=0;
	}
}
inline void solve()
{
	for(int i=1;i<=mp2.cnt;i++)
	if(!dfn[i])
	{
		id++;
		rtson=0;
		tarjan(i,0);
	}
	for(int i=1;i<=c;i++)
	{
		if(vis2[i]) continue;
		top=0;
		getnode(p[i].x,p[i].y,i);
		for(int j=1;j<=top;j++)
		if(to[dui[j]]!=to[dui[1]])
		{
			puts("0");
			return;
		}
	}
	if(n==1||m==1)
	{
		puts("1");
		return;
	}
	for(int i=1;i<=mp2.cnt;i++)
	if(cut[i]&&im[i]==1)
	{
		puts("1");
		return;
	}
	puts("2");
}
inline bool find()
{
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(!mp1.qry(i,j))
			{
				for(int k=0;k<4;k++)
				{
					int x=i+DX[k],y=j+DY[k];
					if(x<1||x>n||y<1||y>m) continue;
					if(!mp1.qry(x,y)) return 1;
				}
				return 0;
			}
		}
	}
	return 0;
}
int main()
{
	int T=read();
	while(T--)
	{
		init();
		n=read(),m=read(),c=read();
		for(int i=1;i<=c;i++)
		{
			p[i].x=read(),p[i].y=read();
			mp1.add(p[i].x,p[i].y);
			
		}
		if((ll)n*m-c<=1||((ll)n*m-c==2&&find()))
		{
			puts("-1");
			continue;
		}
		for(int i=1;i<=c;i++)
		{
			int x=p[i].x,y=p[i].y;
			for(int j=0;j<24;j++)
			{
				int nx=x+dx[j],ny=y+dy[j];
				if(nx<1||nx>n||ny<1||ny>m||mp1.qry(nx,ny)) continue;
				int tmp=mp2.qry(nx,ny);
				if(!tmp)
				{
					mp2.add(nx,ny);
					if(dis(x,y,nx,ny)<1.9) im[mp2.cnt]=1;
					else im[mp2.cnt]=2;
					q[mp2.cnt]=(node){nx,ny};
					
				}
				else
				{
					if(dis(x,y,nx,ny)<1.9) im[tmp]=1;
					else im[tmp]=min(2,im[tmp]);
				}
			}
		}
		for(int i=1;i<=mp2.cnt;i++)
		{
			int x=q[i].x,y=q[i].y;
			for(int j=0;j<4;j++)
			{
				int nx=x+DX[j],ny=y+DY[j];
				if(nx<1||nx>n||ny<1||ny>m) continue;
				int tmp=mp2.qry(nx,ny);
				if(tmp&&im[tmp]) add(i,tmp);
			}
		}
		solve();
	}
	return 0;
}

上一题

© 2024 nowcoder.com