HDU 1198

蔚落 2022-09-22 13:51 20阅读 0赞

并查集

#include<stdio.h>
    #include<string.h>
    #include<algorithm>
    using namespace std;
    char map[11][5]={"1010","1001","0110","0101","1100","0011",  
                   "1011","1110","0111","1101","1111"};  
    int a[10001],n,m;
    char aa[201][201];
    void init()
    {
    	int i;
    	for(i=0;i<=n*m;i++)
    	{
    		a[i]=i;
    	}
    }
    int find(int x)
    {
    	if(x!=a[x])
    	{
    		x=find(a[x]);
    	}
    	return x;
    }
    void un(int x,int y)
    {
    	x=find(x);
    	y=find(y);
    	if(x!=y)
    	a[x]=y;
    }
    int main()
    {
    	int i,j,k,l;
    	while(~scanf("%d %d",&m,&n))
    	{
    		if(n==-1&&m==-1)
    			break;
    		init();
    		for(i=0;i<m;i++)
    		{
    			scanf("%s",&aa[i]);
    		}
    		for(i=0;i<m;i++)
    		{
    			for(j=0;j<n;j++)
    			{
    				if(map[aa[i][j]-'A'][0]=='1'&&map[aa[i-1][j]-'A'][1]=='1'&&i-1>=0)
    				un(i*n+j,(i-1)*n+j);
    				if(map[aa[i][j]-'A'][2]=='1'&&map[aa[i][j-1]-'A'][3]=='1'&&j-1>=0)
    				un(i*n+j,i*n+j-1);
    			}
    		}
    		int cnt=0;
    		for(i=0;i<n*m;i++)
    		{
    			if(a[i]==i)
    			cnt++;
    		}
    		printf("%d\n",cnt);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，20人围观）

还没有评论，来说两句吧...

相关阅读

相关 1198: 零起点学算法105——多项式求和

Description 多项式的描述如下： 1 - 1/2 + 1/3 - 1/4 + 1/5 - 1/6 + ... 现在请你求出该多项式的前n项的和。 I

谁借莪１个温暖的怀抱￠/ 2022年10月26日 14:09/ 0 赞/ 385 阅读

相关 HDU 1198

并查集 include<stdio.h> include<string.h> include<algorithm> using namespa

蔚落/ 2022年09月22日 13:51/ 0 赞/ 21 阅读

相关 Hdu 1198 Farm Irrigation (DFS 异或的应用)

参考了：http://blog.csdn.net/firwaless/article/details/18672239 题意：有一块n\m的农田，被分隔成许多小的正方形，每个

男娘i/ 2022年09月20日 15:09/ 0 赞/ 214 阅读

相关 HDU 1198(并查集;dfs)

题意：给出a-k个图形，求由这些图形拼凑起来的图中的管道一共有几个连通管道。并查集： include<stdio.h> include<st

深碍√TFBOYSˉ_/ 2022年09月20日 11:25/ 0 赞/ 261 阅读

相关 hdu 1198（再续并查集）

/再续并查集 hdu 1198/ include<iostream> include<cstdio> include<cstring>

た入场券/ 2022年08月23日 11:54/ 0 赞/ 160 阅读

相关 Sicily 1198. Substring

思路：对于每一组案例，对数据进行从小到大排序，而后依次输出该组数据。// Problem\: 1198 \include<iostream> usi

短命女/ 2022年08月06日 14:16/ 0 赞/ 366 阅读

相关 HDU - 1198 Farm Irrigation (DFS)

Farm Irrigation Problem Description Benny

分手后的思念是犯贱/ 2022年05月19日 04:25/ 0 赞/ 253 阅读

相关杭电OJ——1198 Farm Irrigation （搜索）（2）

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1198][http_acm.hdu.edu.cn_showproblem.p

心已赠人/ 2021年09月26日 11:34/ 0 赞/ 282 阅读

相关杭电OJ——1198 Farm Irrigation （搜索）

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1198][http_acm.hdu.edu.cn_showproblem.p

偏执的太偏执、/ 2021年09月23日 02:20/ 0 赞/ 296 阅读

相关 1198A MP3（前缀和）

[题目][Link 1] 题意：给一个由n个数字组成的数组，和我们的空间大小I bytes转化为bits即为8\I，该数组有K个不同的数字，对于每个数字我们需要用log

阳光穿透心脏的1/2处/ 2021年07月16日 15:08/ 0 赞/ 414 阅读