[UVALive 6663 Count the Regions] (dfs + 离散化)[通俗易懂]

[UVALive 6663 Count the Regions] (dfs + 离散化)

大家好,又见面了,我是全栈君。

链接:https://icpcarchive.ecs.baylor.edu/index.php?

option=com_onlinejudge&Itemid=8&page=show_problem&problem=4675

题目大意:

在一个平面上有 n (1<=n<=50) 个矩形。给你左上角和右下角的坐标(0<=x<=10^6, 0<=y<=10^6)。问这些矩形将该平面划分为多少块。

解题思路:

因为n非常小,能够对整个图进行压缩。仅仅要不改变每条边的相对位置。对答案没有影响。

能够将这些矩形的坐标离散化,然后把边上的点标记一下。之后进行简单dfs就可以。(注意离散化的时候,两条边之间至少要隔一个距离)

代码:

/*
ID: wuqi9395@126.com
PROG:
LANG: C++
*/
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<vector>
#include<string>
#include<fstream>
#include<cstring>
#include<ctype.h>
#include<iostream>
#include<algorithm>
#define INF (1<<30)
#define PI acos(-1.0)
#define mem(a, b) memset(a, b, sizeof(a))
#define For(i, n) for (int i = 0; i < n; i++)
using namespace std;
const int MOD = 1000000007;
typedef long long ll;
using namespace std;
struct node {
    int a, b, c, d;
} rec[600];
int x[1200], y[1200];
int xp[1000100], yp[1000100];
int mp[240][240], n;
int lx, ly;
void gao() {
    for (int i = 0; i < n; i++) {
        int A = xp[rec[i].a];
        int B = yp[rec[i].b];
        int C = xp[rec[i].c];
        int D = yp[rec[i].d];
        for (int j = A; j <= C; j++) mp[j][D] = mp[j][B] = 1;
        for (int j = D; j <= B; j++) mp[A][j] = mp[C][j] = 1;
    }
}
int dir[4][2] = {{0, -1}, {0, 1}, {1, 0}, { -1, 0}};
bool in(int x, int y) {
    return (x >= 0 && y >= 0 && x < 2 * lx + 1 && y < 2 * ly + 1);
}
void dfs(int x, int y) {
    mp[x][y] = 1;
    for (int i = 0; i < 4; i++) {
        int xx = x + dir[i][0];
        int yy = y + dir[i][1];
        if (in(xx, yy) && !mp[xx][yy]) {
            dfs(xx, yy);
        }
    }
}
int main() {
    while(scanf("%d", &n) != EOF && n) {
        for (int i = 0; i < n; i++) {
            scanf("%d%d%d%d", &rec[i].a, &rec[i].b, &rec[i].c, &rec[i].d);
            x[2 * i] = rec[i].a;
            x[2 * i + 1] = rec[i].c;
            y[2 * i] = rec[i].b;
            y[2 * i + 1] = rec[i].d;
        }
        sort(x, x + 2 * n);
        sort(y, y + 2 * n);
        lx = unique(x, x + 2 * n) - x;
        ly = unique(y, y + 2 * n) - y;
        for (int i = 0; i < lx; i++) {
            xp[x[i]] = 2 * i + 1;
        }
        for (int j = 0; j < ly; j++) {
            yp[y[j]] = 2 * j + 1;
        }
        memset(mp, 0, sizeof(mp));
        gao();
        int fk = 0;
        for (int i = 0; i < 2 * lx; i++) {
            for (int j = 0; j < 2 * ly; j++) if (mp[i][j] == 0) {
                    dfs(i, j);
                    fk++;
                }
        }
        cout << fk << endl;
    }
    return 0;
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/116289.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 为你的爬虫添加 IP 池反反爬策略[通俗易懂]

    为你的爬虫添加 IP 池反反爬策略[通俗易懂]为你的爬虫添加 IP 池反反爬策略

  • pycharm激活【2021最新】

    (pycharm激活)JetBrains旗下有多款编译器工具(如:IntelliJ、WebStorm、PyCharm等)在各编程领域几乎都占据了垄断地位。建立在开源IntelliJ平台之上,过去15年以来,JetBrains一直在不断发展和完善这个平台。这个平台可以针对您的开发工作流进行微调并且能够提供…

  • 倍增

    倍增法可以有很多变化。1.用data[i][j]记录从i到他的第2j个父亲的路径长度,就可以边求LCA边求出两点距离,因为data[i][j]满足倍增的递推式:data[i][j]=data[i][j-1]+data[fa[i][j-1]][j-1]。2.用maxlen[i][j]记录i到第2^j^个父亲的路径上最长边的边权,它满足…

  • 图片加载失败的正确处理[通俗易懂]

    图片加载失败的正确处理[通俗易懂]<imgsrc=”http://imgsrc.baidu.com/forum/pic/item/fd1f4134970a304e16d3176ad3c8a786c8175ca8.jpg”/>对于这样一段代码来讲,如果该图片加载成功,那么界面上会显示图片,如果由于一些原因导致图片加载失败,会出现这样的图标。在正常的项目中,标签的src是后端返回的路径,如果图片加载不出来,显示上…

  • 中国的程序员数量是否已经饱和或者过剩?「建议收藏」

    中国的程序员数量是否已经饱和或者过剩?「建议收藏」根据教育部数据显示:2020年本科毕业生人数874万人。《2020年中国大学生就业报告》显示:计算机类本科生在2020届毕业生数量中稳居前10。每年都有源源不断的新生力量加入程序员大军。另一方面,5G时代到来,对于互联网行业来说,未来将会有更多机会。各大互联网公司进入了新一轮技术资源抢占与加速发展;经过疫情的洗礼,各大传统企业也纷纷加入转型大军,重点发展线上业务;从国家“新基建”的行业分布来看,大多涉及互联网IT行业,预示了未来科学技术的发展走向……可以看到IT行业技术不断更新,专业IT人才随时都处

  • css画圆弧_css圆角样式

    css画圆弧_css圆角样式CSS3是样式表(stylesheet)语言的最新版本,它的一大优点就是支持圆角。网页设计大师NicholasZakas的最新文章,清晰易懂地解释了CSS3圆角的各个方面,非常值得学习。以下就是我翻译的中文版。=========================================CSS3圆角详解作者:NicholasZakas译者:阮一峰发表日期:2010年12月8日一、CSS3…

    2022年10月25日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号