本文共 2540 字，大约阅读时间需要 8 分钟。

终于结束了‘打一题Wa一题’的情况，%%%lyf大佬~~（一眼看破天机）~~

别说了我还有两题都是还没改出来的情况

---

---

Description

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

简单的说，这座设备塔是一个漂浮在异空间中的圆柱体，圆柱体两头的圆是计算核心，而侧面则是 传输信息所用的数据通道，划分成N *m 个区块。 然而，随着工作的继续进行，他们希望把侧面的一部分区块也改造成其他模块。然而，任何时候都 必须保证存在一条数据通道，能从圆柱体的一端通向另一端。 由于无法使用辉之环掌控下的计算系统，他们寻求你的帮助来解决这个问题。他们将逐个输入想要 改造的区域，而你则执行所有可行的改造并忽略可能导致数据中断的改造。

Input

第一行，包含两个整数N;M;K，表示侧面的长和宽，以及操作数。

接下来K 行，每行包含三个整数xi; yi，表示操作的区块的坐标。(0<=y=<M) 数据保证不会对已经操作成功的区块进行操作。

Output

输出一行，表示有多少个操作可以被执行。

Sample Input

3 4 92 23 22 33 43 11 32 11 11 4

Sample Output

6

---

又是一个环，常规操作，将地图复制一个，粘贴到其右侧。于是3* 4的格子变成了3* 8.

思考不可联通的条件：一些填上的格子，环了一圈圆柱。那么从这个格子出发，肯定能再次走到这个格子。我们可以判断：这个格子与复制出来的对应的格子是否联通。用并查集。 但是由于并查集的删点十分麻烦，所以判断这两个格子周围（8格）的格子是否联通就好了。

（诶，，，貌似有点玄学）

#include
   
    int n,m,k,a,b,pd,l1bh,l2bh,Ans,bh1,bh2;int fx[10],B[20000001],f[20000001];int find(int d){      //并查集	if(f[d] == 0 || f[d] == d) return d;	return f[d] = find(f[d]);}int main(){   	scanf("%d%d%d",&n,&m,&k);    //编号从上到下，从左到右。	fx[0] = -2*m-1; fx[1] = -2*m; fx[2] = -2*m+1;  //玄学编号 左上，正上，右上	fx[3] = -1;                   fx[4] = +1;      //左，右	fx[5] = m*2-1; fx[6] = m*2; fx[7] = m*2+1;   //左下，正下，右下	for(int i = 1; i <= k; ++i){   		scanf("%d%d",&a,&b);		l1bh = (a-1) * 2 * m + b;  //得出当前点编号		l2bh = l1bh + m;          //对应点的		pd = 0;		for(int ii = 0; ii < 8 && pd == 0; ++ii){     //相邻的点枚举		    bh1 = l1bh + fx[ii];    //相邻点的编号		    if((l1bh-1) % (2*m) == 0){     //玄学防越界（之前就是这里wa了）		    	if(ii == 0) bh1 = l1bh - 1;		    	if(ii == 3) bh1 = l1bh + 2*m - 1;		    	if(ii == 5) bh1 = l1bh + 4*m -1;		    }		    if(bh1 > 0  && bh1 <= n*m*2)  //在范围内		    if(B[bh1] == 1)		    for(int j = 0; j < 8; ++j){     //同理		        bh2 = l2bh + fx[j];		        if(l2bh % (2*m) == 0){   		        	if(j == 2) bh2 = l2bh - 4*m + 1;		        	if(j == 4) bh2 = l2bh - 2*m + 1;					if(j == 7) bh2 = l2bh + 1; 		        }		        if(bh2 > 0 && bh2 <= n*m*2)		        if(B[bh2] == 1)			    if(find(bh1) == find(bh2)){     //RT			      	  pd = 1;			      	  break;			     }		      }		    } 			if(pd == 0){     //可以放				++Ans;				B[l1bh] = B[l2bh] = 1;  //填上				for(int j = 0; j < 8; ++j){     //并查集					bh1 = l1bh + fx[j];					if((l1bh-1) % (2*m) == 0){     //同上		    		    if(j == 0) bh1 = l1bh - 1;		    		    if(j == 3) bh1 = l1bh + 2*m - 1;		    		    if(j == 5) bh1 = l1bh + 4*m - 1;		    	    }		    	    if(((bh1 - 1) / m) % 2 == 0) bh2 = bh1+m;		    	    else bh2 = bh1-m;					if(bh1 > 0 && bh1 <= n*m*2)					if(B[bh1] == 1){   				  	    f[find(l1bh)] = find(bh1);				  	    f[find(l2bh)] = find(bh2);				    }				}				  			}	}	printf("%d",Ans);}
   

转载地址：http://qqkg.baihongyu.com/