题目

为了封印辉之环，古代塞姆利亚大陆的人民在异空间中建造了一座设备塔。

简单的说，这座设备塔是一个漂浮在异空间中的圆柱体，圆柱体两头的圆是计算核心，而侧面则是

传输信息所用的数据通道，划分成N *m 个区块。

然而，随着工作的继续进行，他们希望把侧面的一部分区块也改造成其他模块。然而，任何时候都

必须保证存在一条数据通道，能从圆柱体的一端通向另一端。

由于无法使用辉之环掌控下的计算系统，他们寻求你的帮助来解决这个问题。他们将逐个输入想要

改造的区域，而你则执行所有可行的改造并忽略可能导致数据中断的改造。

分析

圆柱体，所以左右两边相通。将这N*M个区块复制一个，并起来。

发现，如有有两个区块都被改造了，那么当其中个区块是在另一个区块的八个方向相邻的话，数据就不能从之间通过。

于是，我们搞个并查集，当改造一个区块时，如果在改造后，与之对应的被复制的区块，在并查集中有共同的父亲，那么这个区块就不合法，因为当区块和被复制的区块中可以通过区块相连，又因为每个区块都有对应的被复制的区块，显然整个圆柱体就一定被挡住了。

如果这个区块合法，那么将它八个方向相邻的区块中被改造的都和他用并查集合在一起。

有个小细节要就是当某个区块的八个方向相邻的区块中有列数小于1或大于2m的要处理一下。

#include <cmath>

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

#include <queue>

const int maxlongint=2147483647;

const int mo=1000000007;

const int N=3005;

using namespace std;

int k,n,m,fa[N*N*2],a[N][N*2],ans;

int z[8][2]=

{

	{-1,0},

	{0,-1},

	{1,0},

	{0,1},

	{-1,1},

	{1,-1},

	{1,1},

	{-1,-1}

};

int pos(int x,int y)

{

	return (x-1)*m*2+y;

}

int get(int x)

{

	if(fa[x]==x) return x;

	fa[x]=get(fa[x]);

	return fa[x];

}

int main()

{

	scanf("%d%d%d",&n,&m,&k);

	for(int i=1;i<=n*m*2;i++) fa[i]=i;

	for(k=k;k>=1;k--)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		int xx=x,yy=y+m;

		bool q=true;

		for(int i=0;i<=7 && q;i++)

			if(a[x+z[i][0]][(y+z[i][1]-1+2*m)%(2*m)+1])

			{

				int xf=get(pos(x+z[i][0],(y+z[i][1]-1+2*m)%(2*m)+1));

				for(int j=0;j<=7 && q;j++)

					if(a[xx+z[j][0]][(yy+z[j][1]-1+2*m)%(2*m)+1])

					{

						int yf=get(pos(xx+z[j][0],(yy+z[j][1]-1+2*m)%(2*m)+1));

						if(xf==yf) q=false;

					}

			}

		if(q)

		{

			a[x][y]=a[xx][yy]=1;

			for(int i=0;i<=7;i++)

				if(a[x+z[i][0]][(y+z[i][1]-1+2*m)%(2*m)+1])

				{

					int xf=get(pos(x+z[i][0],(y+z[i][1]-1+2*m)%(2*m)+1));

					fa[xf]=pos(x,y);

				}

			for(int j=0;j<=7;j++)

				if(a[xx+z[j][0]][(yy+z[j][1]-1+2*m)%(2*m)+1])

				{

					int yf=get(pos(xx+z[j][0],(yy+z[j][1]-1+2*m)%(2*m)+1));

					fa[yf]=pos(xx,yy);

				}

			ans++;

		}

	}

	cout<<ans<<endl;

}

巴特西

【NOIP2014模拟8.25】设备塔

题目

分析

最新文章

热门文章