首页 > 其他分享 >「NOI2016」网格 题解

「NOI2016」网格 题解

时间：2022-08-27 11:33:31浏览次数：135  
标签：障碍物 题解 ll NOI2016 网格 yy vis xx continue

「NOI2016」网格 题解

前言

感谢 zqm 学长提供调代码服务！

本文中，所有没有特殊说明的连通都是指四连通，相邻都是指上下左右相邻。

题目大意

有一个 $ n \times m $ 的网格，上面有 $ c $ 个障碍物，求至少还需要多少个障碍物才能使空地不连通。

输入

第一行有一个整数 $ T $，表示数据组数。

每组数据的第一行有三个整数 $ n,m,c $。

接下来 $ c $，每行两个整数 $ x,y $，表示第 $ x $ 行第 $ y $ 列有一个障碍物。保证每个障碍物不会被多次描述。

输出

一个整数，表示答案。

数据范围

$ 1 \le T \le 20 $

$ n,m \le 10^9 $

$ \sum c \le 10^5 $

思路

分析题目发现，当一个空地在角上的时候，答案最大为 $ 2 $，而如果角上是障碍物，又会形成一个新的角，所以本题答案只有 $ -1,0,1,2 $ 四种情况。我们可以分类讨论。

注意，这里的分类讨论是有顺序的，只有当前面的条件不满足才会判断后面的条件。

  • 当答案为 $ -1 $ 时：

    • 空地本来就少于两个。

      此时只需要判断 $ n \times m - c $ 是否小于 $ 2 $。

    • 有两个相邻的空地。

      此时在 $ n \times m - c = 2 $ 的基础上，需要记录每行每列的障碍物数量，进一步判断是否相邻。

  • 当答案为 $ 0 $ 时：

    • 有一坨障碍物已经使得空地不连通。

      由于障碍物较少，考虑从障碍物入手，然后找到对计算答案有用的空地，进行统计。

      我们可以证明，若存在这样一坨障碍物，则这坨障碍物必定为一个八连通分量。

      我们可以利用这个性质，依次找出障碍物组成的每个八连通分量，再将所有与当前八连通分量八连通的空地找出，把相邻的空地连边，看是否连通即可。

  • 当答案为 $ 1 $ 时：

    • 网格只有一行或一列。

    • 网格中存在一个点，使得将它变成障碍物后空地不连通。

      可以发现，这跟割点的定义相同，考虑类比上方的思路，找到有用的空地，相邻的空地连边，建图求割点。

      我们想到，可以同样找与障碍物八连通的空地。但是看下面这种情况（X 表示障碍，. 表示空地，1 表示选的点）：

      .......
.111...
.1X1...
.11111.
...1X1.
...111.
.......

      此时会把中间的 1 判为割点，但是它并不是整个网格图的割点。

      所以我们考虑再拓展一层，变成这样：（2 表示第二次拓展的点）

      22222..
21112..
21X1222
2111112
2221X12
..21112
..22222

      可以证明，此时如果标为 1 的点是我们建出来的图的割点，那么这个点一定是整个网格图的割点。（证明被咕了，但是可以感性理解一下）

  • 其余情况答案为 $ 2 $。

别看代码很长，实际上不难。代码中有注释，非常简洁易懂。

对了，这道题需要手写 hash，但是我太弱了，所以就使用 卡常 + Ofast 之力 卡到了 1950ms（逃

代码实现

#include<bits/stdc++.h>
#define ll int
const ll N=4e7+10;
using namespace std;

ll nt[8][2]={0,1,1,0,0,-1,-1,0,1,1,1,-1,-1,1,-1,-1};//判断连通 
ll T,n,m,c,x[N],y[N];//题目输入的变量 
ll sx[N],sy[N];//判断无解，统计有空地的行和列 
map<pair<ll,ll>,ll>a;//记录障碍 
map<pair<ll,ll>,ll>vis;//记录有用的点，辅助建图 
ll cnt,v[N],fir[N],nxt[N];//邻接表 
ll visit[N];//判断答案为 0，标记是否被访问 
ll vvv[N];//判断答案为 0，bfs2，标记数组 
ll flag;//判断答案为 1，标记是否有割点 
ll num,dfn[N],low[N];//判断答案为 1，tarjan 
ll tags[N];//判断答案为 1，标记第一层八连通空地 

ll read(){//快读 
	ll s=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')f=(ch=='-'?-1:1),ch=getchar();
	while(ch>='0'&&ch<='9')s=s*10+(ch^48),ch=getchar();
	return f*s;
}

void add(ll x,ll y){//连边 
	v[++cnt]=y;
	nxt[cnt]=fir[x];
	fir[x]=cnt;
}

ll bfs2(ll st){//普通的 bfs 
	ll tot=1;
	queue<ll>q;
	q.push(st);
	vvv[st]=1;
	while(!q.empty()){
		ll x=q.front();
		q.pop();
		for(ll i=fir[x];i;i=nxt[i]){
			ll y=v[i];
			if(vvv[y])continue;
			vvv[y]=1;
			q.push(y);
			++tot;
		}
	}
	return tot;
}

bool bfs1(ll st){//找八连通障碍物并建图 
	//初始化 
	vis.clear();
	cnt=0;
	queue<ll>tmp;//记录八连通障碍物 
	queue<ll>q;
	tmp.push(st);//记录 
	q.push(st);
	visit[st]=1;
	while(!q.empty()){
		ll i=q.front();
		q.pop();
		for(ll j=0;j<8;++j){//这里是八连通 
			ll xx=x[i]+nt[j][0];
			ll yy=y[i]+nt[j][1];
			if(xx<1||xx>n||yy<1||yy>m)continue;//出界 
			if(a.find({xx,yy})==a.end())continue;//不是障碍物 
			if(visit[a[{xx,yy}]])continue;//访问过 
			visit[a[{xx,yy}]]=1;//标记 
			tmp.push(a[{xx,yy}]);//记录 
			q.push(a[{xx,yy}]);
		}
	}
	ll tot=0;
	while(!tmp.empty()){
		auto i=tmp.front();
		tmp.pop();
		for(ll j=0;j<8;++j){//这里是八连通 
			ll xx=x[i]+nt[j][0];
			ll yy=y[i]+nt[j][1];
			if(xx<1||xx>n||yy<1||yy>m)continue;//出界 
			if(vis.find({xx,yy})!=vis.end())continue;//已经标记过 
			if(a.find({xx,yy})!=a.end())continue;//是障碍物 
			vis[{xx,yy}]=++tot;//标记点号 
		}
	}
	for(ll i=1;i<=tot;++i)fir[i]=0;//初始化 
	//给有用的点连边 
	for(auto i:vis){
		ll x=i.first.first;
		ll y=i.first.second;
		ll t=i.second;
		for(ll i=0;i<4;++i){//这里是四连通 
			ll xx=x+nt[i][0];
			ll yy=y+nt[i][1];
			if(xx<1||xx>n||yy<1||yy>m)continue;//出界 
			if(vis.find({xx,yy})==vis.end())continue;//没有标记过 
			//连边 
			add(t,vis[{xx,yy}]);
		}
	}
	for(ll i=1;i<=tot;++i)vvv[i]=0;//初始化 
	ll cnt=bfs2(1);
	if(cnt!=tot)return true;
	return false;
}

void tarjan(ll x,ll fa){//tarjan 求割点 
	dfn[x]=low[x]=++num;
	ll tot=0;
	for(ll i=fir[x];i;i=nxt[i]){
		ll y=v[i];
		if(!dfn[y]){
			tarjan(y,x);
			low[x]=min(low[x],low[y]);
			if(low[y]>=dfn[x]){
				tot++;
				if(fa||tot>1){
					if(tags[x])flag=1;//当求出来的割点为第一层空地时才是真正的割点 
				}
			}
		}else{
			low[x]=min(low[x],dfn[y]);
		}
	}
}

bool judge_no_solution_1(){//无解：少于两个空地 
	return (long long)n*m-c<2;
}

bool judge_no_solution_2(){//无解：有两个四连通相邻的空地 
	if((long long)n*m-c!=2)return false;
	//初始化 
	for(ll i=1;i<=n;++i)sx[i]=0;
	for(ll i=1;i<=m;++i)sy[i]=0;
	//统计每行每列障碍物总数 
	for(ll i=1;i<=c;++i){
		sx[x[i]]++;
		sy[y[i]]++;
	}
	//找有空地的行 
	ll x1=0,x2=0;
	for(ll i=1;i<=n;++i){
		if(sx[i]<m){
			if(!x1)x1=i;
			else x2=i;
		}
	}
	//找有空地的列 
	ll y1=0,y2=0;
	for(ll i=1;i<=m;++i){
		if(sy[i]<n){
			if(!y1)y1=i;
			else y2=i;
		}
	}
	if((abs(x1-x2)==1&&y1&&!y2)||(x1&&!x2&&abs(y1-y2)==1)){//判断是否连通 
		return true;
	}
	return false;
}

bool judge_one_1(){//只有一行或一列 
	return n==1||m==1;
}

bool judge_zero(){
	//初始化 
	a.clear();
	for(ll i=1;i<=c;++i){
		visit[i]=0;
	}
	//标记障碍物 
	for(ll i=1;i<=c;++i){
		a[{x[i],y[i]}]=i;
	}
	for(ll i=1;i<=c;++i){
		if(visit[i])continue;//访问过 
		if(bfs1(i))return true;
	}
	return false;
}

bool judge_one_2(){//有割点 
	//初始化 
	flag=0;
	num=0;
	a.clear();
	vis.clear();
	cnt=0;
	//标记障碍物 
	for(ll i=1;i<=c;++i){
		a[{x[i],y[i]}]=1;
	}
	//找有用的点 
	ll tot=0;
	for(ll i=1;i<=c;++i){
		for(ll j=0;j<8;++j){//这里是八连通 
			ll xx=x[i]+nt[j][0];
			ll yy=y[i]+nt[j][1];
			if(xx<1||xx>n||yy<1||yy>m)continue;//出界 
			if(vis.find({xx,yy})!=vis.end())continue;//已经标记过 
			if(a.find({xx,yy})!=a.end())continue;//是障碍物 
			vis[{xx,yy}]=++tot;//标记点号 
		}
	}
	map<pair<ll,ll>,ll>VIS;//临时存储第二层点，为了防止遍历 vis 时爆炸 
	ll ___=tot;
	//再拓展一层 
	for(auto i:vis){
		ll x=i.first.first;
		ll y=i.first.second;
		ll t=i.second;
		for(ll i=0;i<8;++i){//这里是八连通 
			ll xx=x+nt[i][0];
			ll yy=y+nt[i][1];
			if(xx<1||xx>n||yy<1||yy>m)continue;//出界 
			if(vis.find({xx,yy})!=vis.end()||VIS.find({xx,yy})!=VIS.end())continue;//标记过 
			if(a.find({xx,yy})!=a.end())continue;//是障碍物 
			VIS[{xx,yy}]=++tot;
		}
	}
	//初始化 
	for(ll i=1;i<=___;++i)tags[i]=1;
	for(ll i=___+1;i<=tot;++i)tags[i]=0;
	//转移至 vis 
	for(auto i:VIS){
		ll x=i.first.first;
		ll y=i.first.second;
		ll t=i.second;
		vis[{x,y}]=t;
	}
	for(ll i=1;i<=tot;++i)fir[i]=0;
	//给有用的点连边 
	for(auto i:vis){
		ll x=i.first.first;
		ll y=i.first.second;
		ll t=i.second;
		for(ll i=0;i<4;++i){//这里是四连通 
			ll xx=x+nt[i][0];
			ll yy=y+nt[i][1];
			if(xx<1||xx>n||yy<1||yy>m)continue;//出界 
			if(vis.find({xx,yy})==vis.end())continue;//没有标记过 
			//连边 
			add(t,vis[{xx,yy}]);
		}
	}
	for(ll i=1;i<=tot;++i)dfn[i]=low[i]=0;//初始化 
	for(ll i=1;i<=tot;++i){
		if(!dfn[i]){
			tarjan(i,0);
		}
	}
	if(flag)return true;
	return false;
}

int main(){
	
	T=read();
	while(T--){
		n=read();
		m=read();
		c=read();
		for(ll i=1;i<=c;++i){
			x[i]=read();
			y[i]=read();
		}
		//无解 
		if(judge_no_solution_1()){
			printf("-1\n");
			continue;
		}
		if(judge_no_solution_2()){
			printf("-1\n");
			continue;
		}
		//答案为 0 
		if(judge_zero()){
			printf("0\n");
			continue;
		}
		//答案为 1 
		if(judge_one_1()){
			printf("1\n");
			continue;
		}
		if(judge_one_2()){
			printf("1\n");
			continue;
		}
		//答案为 2 
		printf("2\n");
	}
	
	return 0;
}

总结

在代码改动的时候，一定要注意将相关的其它函数都看一眼，否则可能会造成不必要的损失。请记住，板子不是一成不变的，要知道每个位置什么意思。（我就是因为改 bfs1 的实现方法时没改该死的 tarjan 判割点的条件，挂了好久）

一般来说，多组测试卡常效果最好的还是将 memset 改成 for 暴力赋值。虽然 memset 快一些，但它会将整个数组都更改，我们用不到的也被更改了。如果我们只更改有用的，效率可能更高。

尾声

如果你发现了问题，你可以直接回复这篇题解

如果你有更好的想法，也可以直接回复！

标签：障碍物,题解,ll,NOI2016,网格,yy,vis,xx,continue
From： https://www.cnblogs.com/zsc985246/p/16621315.html

相关文章

  • 【IAP Kit】应用内支付订单参数相关问题解析
    ​1、创建的订单orderId长度是多少？答：orderId的长度最大是255。 2、InappPurchaseDetails中orderId和payOrderId有什么区别呢？答：orderId和payOrderId这两者的区别如下：o......
  • 优先队列-多路归并系列题解
    373.查找和最小的K对数字问题描述给定两个以升序排列的整数数组nums1和nums2 , 以及一个整数k 。定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来......
  • 【题解】CF1007D Ants
    传送门题意：有\(m\)对链，每对链要选择一条，使得选择的链两两不交，求一组方案。题解：一眼看上去就是一个2-sat，考虑一种暴力的做法，枚举每一条边，覆盖这条边的链两两连边。......
  • 题解 UVA10791
    前言：数学符号约定：\(p\)：任意一个质数\(n\)或\(m\)：任意一个正整数\(a_i\)：唯一分解时质数的指数\(A\)：集合若无特殊说明，本篇题解的数学符号将会严格按照上......
  • 20220823 模拟赛题解
    T1文件压缩DecriptionlinkSolution可以根据\(S'\)和\(p\)求出第一个字符，然后把\(S'\)sort一遍后得到字符串\(T\)，那么我们就可以求出每一个字符的前驱和后继，所......
  • LeetCode 链表的中间结点算法题解 All In One
    LeetCode链表的中间结点算法题解AllInOnejs/ts实现重排链表链表的中间结点原理图解//快慢指针functionmiddleNode(head:ListNode|null):ListNode|n......
  • k8s问题解决
    问题1：问题描述：k8s中Terminating状态pod不能删除[root@master~]#kubectlgetpods-nmsNAMEREADYSTATUSRESTARTSAGEportal-78......
  • Unable to create an object of type 'DbContext'问题解决，网上搜来的没一个对的。
    用了很久的EFCore了，第一次遇到这个问题，觉得很奇怪，baidu了一下，都是要提供设计时工厂的答案。很明显这个做法是有问题的，都是DI的年代了，你的DbContext又不是动态生产了一堆......
  • P1399 [NOI2013] 快餐店 题解
    题目大意求一棵基环树的重心。即一个点，使得树上到其距离最长的点到其的距离最短。注意，这个点不一定是一个节点，可以在树上的任意位置。输出树上到其距离最长的点到其的距离......
  • P8443 题解
    前言题目传送门！更好的阅读体验？普及组月赛第一题。别的题解语言有点高深，我补篇题解。思路显然，\(\lfloor\dfrac{l}{x}\rfloor,\lfloor\dfrac{l+1}{x}\rfloor,\cdot......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99