当前位置:网站首页>[UVALive 6663 Count the Regions] (dfs + 离散化)[通俗易懂]
[UVALive 6663 Count the Regions] (dfs + 离散化)[通俗易懂]
2022-07-07 20:58:00 【全栈程序员站长】
大家好,又见面了,我是全栈君。
题目大意:
在一个平面上有 n (1<=n<=50) 个矩形。给你左上角和右下角的坐标(0<=x<=10^6, 0<=y<=10^6)。问这些矩形将该平面划分为多少块。
解题思路:
因为n非常小,能够对整个图进行压缩。仅仅要不改变每条边的相对位置。对答案没有影响。
能够将这些矩形的坐标离散化,然后把边上的点标记一下。之后进行简单dfs就可以。(注意离散化的时候,两条边之间至少要隔一个距离)
代码:
/*
ID: [email protected]
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;
}
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116289.html原文链接:https://javaforall.cn
边栏推荐
- I wrote a markdown command line gadget, hoping to improve the efficiency of sending documents by garden friends!
- C语言多角度帮助你深入理解指针(1. 字符指针2. 数组指针和 指针数组 、数组传参和指针传参3. 函数指针4. 函数指针数组5. 指向函数指针数组的指针6. 回调函数)
- AADL inspector fault tree safety analysis module
- 不落人后!简单好用的低代码开发,快速搭建智慧管理信息系统
- 凌云出海记 | 易点天下&华为云:推动中国电商企业品牌全球化
- Flask1.1.4 Werkzeug1.0.1 源码分析:路由
- sqlHelper的增删改查
- 论文解读(ValidUtil)《Rethinking the Setting of Semi-supervised Learning on Graphs》
- 数值法求解最优控制问题(〇)——定义
- Is it safe to open a stock account at present? Can I open an account online directly.
猜你喜欢
Don't fall behind! Simple and easy-to-use low code development to quickly build an intelligent management information system
使用枚举实现英文转盲文
神兵利器——敏感文件发现工具
Implement secondary index with Gaussian redis
95年专注安全这一件事 沃尔沃未来聚焦智能驾驶与电气化领域安全
【C语言】指针进阶---指针你真的学懂了吗?
OneSpin 360 DV新版发布,刷新FPGA形式化验证功能体验
恶魔奶爸 B3 少量泛读,完成两万词汇量+
How to meet the dual needs of security and confidentiality of medical devices?
Details of C language integer and floating-point data storage in memory (including details of original code, inverse code, complement, size end storage, etc.)
随机推荐
Is it safe to open an account of BOC shares in kainiu in 2022?
华泰证券可以做到万一佣金吗,万一开户安全嘛
智能软件分析平台Embold
Deep learning model compression and acceleration technology (VII): mixed mode
Micro service remote debug, nocalhost + rainbow micro service development second bullet
Optimization cases of complex factor calculation: deep imbalance, buying and selling pressure index, volatility calculation
目前股票开户安全吗?可以直接网上开户吗。
开户必须往账户里面赚钱吗,资金安全吗?
恶魔奶爸 A1 语音听力初挑战
FTP steps for downloading files from Huawei CE switches
201215-03-19—cocos2dx内存管理–具体解释「建议收藏」
Codesonar Webinar
凌云出海记 | 赛盒&华为云:共助跨境电商行业可持续发展
C语言多角度帮助你深入理解指针(1. 字符指针2. 数组指针和 指针数组 、数组传参和指针传参3. 函数指针4. 函数指针数组5. 指向函数指针数组的指针6. 回调函数)
Small guide for rapid formation of manipulator (12): inverse kinematics analysis
寫一下跳錶
Tensorflow2.x下如何运行1.x的代码
恶魔奶爸 B2 突破语法,完成正统口语练习
恶魔奶爸 B3 少量泛读,完成两万词汇量+
机械臂速成小指南(十一):坐标系的标准命名