题解 P1451 【求细胞数量】

· · 题解

虽然这题已经有45篇题解，但没有一个人想用并查集呢~

介绍一种思考难度稍大的方法

1.Begin

（看见题面马上就知道是Floodfill

但因为一些原因，NOIP暂停，我想到了区间维护就换了种做法

注意！开始讲题（敲黑板）

样例搬运~

4  10
0234500067
1034560500
2045600671
0000000089

我们可以认为，在某行的数据可表示为（如第一行）

数值：0，2，3，4，5，0，0，0，6，7

位置：1，2，3，4，5，6，7，8，9，10

在[2,5] ， [9,10]处有数据

同理，第二行中，[1,1]，[3,6]，[8,8]有数据

你看看

这一行的[3,6]与上一行的[2,5]有交集，所以他们应该在同一联通块中

2.Naive

你要真的这么想，就图样图森破了

那么我想反问一句，为什么不从下往上连呢

当然可以

因为往下连边可以减少find次数期望，推倒不难。但笔者不会

LATEX

就不用了罢

以下是代码（直接复制并粘贴有惊喜哦）

//能不用尽量别用，O(N*M) 
//27ms
#include<cstdio>
int n,m,a[101][101];//a就是地图 
int tot=0,fa[10010],stlst/*上一行的起始*/,stnow/*这一行的起始*/,qj[10010][2];
int find(int u)
{
    return u==fa[u]?u:fa[u]=find(fa[u]);//板子 
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            scanf("%1d",&a[i][j]);//鸣谢最上面的题解 
    for(int i=1;(i<<1)<=n*m;i++) fa[i]=i;//最多N*M/2个块 
    for(int i=1;i<=n;i++)
    {
        stlst=stnow;
        stnow=tot;
        for(int j=1;j<=m;j++)
            if(a[i][j])
            {
                qj[tot][0]=j;
                while(a[i][j]) j++;
                qj[tot][1]=j-1;
                for(int k=stlst;k<stnow;k++)
                    if(qj[k][1]>=qj[tot][0]&&qj[k][0]<=qj[tot][1]) fa[find(k)]=tot;
                tot++;
            }
    }
    int ans=0;
    for(int i=tot-1;i>=0;i--) if(fa[i]==i)/*我上面没有人*/ ans++;
    printf("%d",ans);
}
//People who copied will AK IOI!

一片苦心孤诣……可怜可怜我吧……给个赞叭~