Farm Irrigation

题意:判断图中的图形有几个集合。

        这道题做的郁闷死我了,为了找开始字母的错误一个一个匹对。

        这道题让我也懂得了表格的位置可以代表并查集的点,这样每个都不一样,而我想的那种用字母是否本身来判断有多少个集合是错误的,很明显一个字母不会只出现一次。而且在计算位置的时候也出错了,应该i*列代表的第几行

#include<stdio.h>
#include<string.h>
const int MAXN=110;
int total;
int gra_row[MAXN][MAXN],gra_col[MAXN][MAXN];
int rank[2510],father[2510];

void init()
{
   memset(gra_row,0,sizeof(gra_row));
   memset(gra_col,0,sizeof(gra_col));
   gra_row['B']['A']=gra_row['B']['C']=gra_row['B']['F']=gra_row['B']['G']=gra_row['B']['H']=gra_row['B']['I']=gra_row['B']['K']=1;
   gra_row['D']['A']=gra_row['D']['C']=gra_row['D']['F']=gra_row['D']['G']=gra_row['D']['H']=gra_row['D']['I']=gra_row['D']['K']=1;
   gra_row['F']['A']=gra_row['F']['C']=gra_row['F']['F']=gra_row['F']['G']=gra_row['F']['H']=gra_row['F']['I']=gra_row['F']['K']=1;
   gra_row['G']['A']=gra_row['G']['C']=gra_row['G']['F']=gra_row['G']['G']=gra_row['G']['H']=gra_row['G']['I']=gra_row['G']['K']=1;
   gra_row['I']['A']=gra_row['I']['C']=gra_row['I']['F']=gra_row['I']['G']=gra_row['I']['H']=gra_row['I']['I']=gra_row['I']['K']=1;
   gra_row['J']['A']=gra_row['J']['C']=gra_row['J']['F']=gra_row['J']['G']=gra_row['J']['H']=gra_row['J']['I']=gra_row['J']['K']=1;
   gra_row['K']['A']=gra_row['K']['C']=gra_row['K']['F']=gra_row['K']['G']=gra_row['K']['H']=gra_row['K']['I']=gra_row['K']['K']=1;



   gra_col['C']['A']=gra_col['C']['B']=gra_col['C']['E']=gra_col['C']['G']=gra_col['C']['H']=gra_col['C']['J']=gra_col['C']['K']=1;
   gra_col['D']['A']=gra_col['D']['B']=gra_col['D']['E']=gra_col['D']['G']=gra_col['D']['H']=gra_col['D']['J']=gra_col['D']['K']=1;
   gra_col['E']['A']=gra_col['E']['B']=gra_col['E']['E']=gra_col['E']['G']=gra_col['E']['H']=gra_col['E']['J']=gra_col['E']['K']=1;
   gra_col['H']['A']=gra_col['H']['B']=gra_col['H']['E']=gra_col['H']['G']=gra_col['H']['H']=gra_col['H']['J']=gra_col['H']['K']=1;
   gra_col['I']['A']=gra_col['I']['B']=gra_col['I']['E']=gra_col['I']['G']=gra_col['I']['H']=gra_col['I']['J']=gra_col['I']['K']=1;
   gra_col['J']['A']=gra_col['J']['B']=gra_col['J']['E']=gra_col['J']['G']=gra_col['J']['H']=gra_col['J']['J']=gra_col['J']['K']=1;
   gra_col['K']['A']=gra_col['K']['B']=gra_col['K']['E']=gra_col['K']['G']=gra_col['K']['H']=gra_col['K']['J']=gra_col['K']['K']=1;

}

void Make_set()
{
    for(int i=0;i<=2505;i++)
    {
        father[i]=i;
        rank[i]=0;
    }
}

int Find(int x)
{
    if(x!=father[x])
    {
        return father[x]=Find(father[x]);
    }
    return x;
}
void Union(int x,int y)
{
    x=Find(x);
    y=Find(y);
    if(x==y) return ;
    total--;
    if(rank[x]>rank[y]) father[y]=x;
    else
    {
        if(rank[x]==rank[y])
        {
            rank[y]++;
        }
        father[x]=y;
    }
}
int main()
{
    int n,m,i,j;
    int a,b;
    char str[MAXN][MAXN];
    init();
    while(scanf("%d%d",&n,&m))
    {
        Make_set();
        memset(str,0,sizeof(str));
        total=m*n;
        if(m<0 || n<0) break;
        for(i=0;i<n;i++)
        {
            scanf("%s",str[i]);
        }
        for(i=0;i<n;i++)
        {
            for(j=0;j<m;j++)
            {
                if(gra_row[str[i][j]][str[i][j+1]]==1) //Union(str[i][j],str[i][j+1]);
                {
                    a=i*m+j;
                    b=a+1;
                    Union(a,b);
                }
                if(gra_col[str[i][j]][str[i+1][j]]==1) //Union(str[i][j],str[i+1][j]);
                {
                    a=i*m+j;
                    b=(i+1)*m+j;
                    Union(a,b);
                }
            }
        }
        printf("%d\n",total);
    }
    return 0;
}

简便一点的写法

char up[8]={"ABEGHJK"},
        down[8]={"CDEHIJK"},
        left[8]={"ACFGHIK"},
        right[8]={"BDFGIJK"};
int row_link[30][30]={0},column_link[30][30]={0};
void init()
{
    int i,j;
    for(i=0;i<7;i++)
    {
         for(j=0;j<7;j++)
        {
            column_link[down[i]-'A'][up[j]-'A']=1;
            row_link[right[i]-'A'][left[j]-'A']=1;
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

06:笨小猴

06:笨小猴 总时间限制:1000ms内存限制:65536kB描述 笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用...

3357
来自专栏desperate633

LintCode 奇偶分割数组题目分析代码

751
来自专栏和蔼的张星的图像处理专栏

730. 所有子集的和递归

给一整数 n, 我们需要求前n个自然数形成的集合的所有可能子集中所有元素的和 样例

1302
来自专栏架构之路

并查集Union-find及其在最小生成树中的应用

并查集是一种用途广泛的数据结构,能够快速地处理集合的合并和查询问题,并且实现起来非常方便,在很多场合中都有着非常巧妙的应用,。 本文首先介绍并查集的定义、原理及...

3484
来自专栏云端架构

【云端架构】教你口算MD5算法

对MD5算法简要的叙述可以为:MD5以512位分组来处理输入的信息,且每一分组又被划分为16个32位子分组,经过了一系列的处理后,算法的输出由四个32位分组组成...

58214
来自专栏余林丰

8.动态规划(1)——字符串的编辑距离

  动态规划的算法题往往都是各大公司笔试题的常客。在不少算法类的微信公众号中,关于“动态规划”的文章屡见不鲜,都在试图用最浅显易懂的文字来描述讲解动态规划,甚至...

62510
来自专栏chenjx85的技术专栏

leetcode-476-Number Complement

1735
来自专栏desperate633

LeetCode 149. Max Points on a Line分析代码

将x,y的差值求最大公约数,约到最简洁的形式,然后存入map中,对每个点这样操作,如果最后x,y最后相等,那么就说明两个点具有相同的斜率,在一条直线上。同时不要...

953
来自专栏数据结构与算法

P3382 【模板】三分法

题目描述 如题,给出一个N次函数,保证在范围[l,r]内存在一点x,使得[l,x]上单调增,[x,r]上单调减。试求出x的值。 输入输出格式 输入格式: 第一行...

3469
来自专栏数据结构与算法

洛谷P3966 [TJOI2013]单词(AC自动机)

1022

扫码关注云+社区

领取腾讯云代金券