并查集 --cogs456 岛国

题目链接：http://cogs.pro:8081/cogs/problem/problem.php?pid=pNyNQiqge

思路：

基础是并查集，将两个相邻的岛算作一个集合，每次若合并成功，则N--，最终得到的即为答案。

先按读入岛的x1进行升序排序，然后遍历每个节点，对于节点i，取之后的j，并且要求 j 的x1 <= i 的x2 + 1，之后进行判断

判断内容为：

如果i的y2小于j的y1 - 1，或者i的y1大于等于j的y2 + 1，即两块陆地在x坐标上未有交集且不相邻，则return false。

如果i的x2 + 1 == j的x1：

此时，如果i的y2 + 1 == j的y1 说明两块陆地只有一个点相交，return false

否则，就return true

代码如下：

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>

#include <cstdio>

#include <algorithm>

#define MAXN 10010

using namespace std;

int n, ct;

int pre[MAXN];

struct Land

{

    int x1, y1, x2, y2;

    bool operator<(const Land& a)const

    {

        if (x1 != a.x1)

            return x1 < a.x1;

        return y1 < a.y1;

    }

}land[MAXN];

int find(int x)

{

    if (x == pre[x])

        return x;

    return pre[x] = find(pre[x]);

}

int Union(int x, int y)

{

    int xPre = find(x);

    int yPre = find(y);

    if (xPre == yPre)

        return ;

    else

    {

        pre[xPre] = yPre;

        return ;

    }

}

int judge(const Land& a, const Land& b)

{

    if (a.y1 -  > b.y2 || a.y2 +  < b.y1)

        return ;

    if (a.x2 +  == b.x1)

    {

        if (a.y1 -  == b.y2 || a.y2 +  == b.y1)

            return ;

        else

            return ;

    }

    else

        return ;

}

int main()

{

    freopen("jx.in", "r", stdin);

    freopen("jx.out", "w", stdout);

    scanf("%d", &n);

    ct = n;

    for (int i = ; i < n; i++)

    {

        scanf("%d %d %d %d", &land[i].x1, &land[i].y1, &land[i].x2, &land[i].y2);

        pre[i] = i;

    }

    sort(land, land + n);

    for (int i = ; i < n; i++)

    {

        for(int j = i + ; j < n && land[j].x1 <= land[i].x2 + ; j++)

            if (judge(land[i], land[j]) && Union(i, j))

            {

                ct--;

            }

    }

    printf("%d\n", ct);

    return ;

}

巴特西

并查集 --cogs456 岛国

最新文章

热门文章