当前位置:网站首页>[uvalive 6663 count the regions] (DFS + discretization) [easy to understand]
[uvalive 6663 count the regions] (DFS + discretization) [easy to understand]
2022-07-07 20:59:00 【Full stack programmer webmaster】
Hello everyone , I meet you again , I'm the king of the whole stack .
The main idea of the topic :
There are... On a plane n (1<=n<=50) A rectangle . Give you the coordinates of the upper left corner and the lower right corner (0<=x<=10^6, 0<=y<=10^6). Ask how many blocks these rectangles divide the plane .
Their thinking :
because n A very small , It can compress the whole graph . Just don't change the relative position of each side . It has no effect on the answer .
The coordinates of these rectangles can be discretized , Then mark the dot on the side . After that, simple dfs Can .( Pay attention to discretization , There should be at least a distance between the two sides )
Code :
/*
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;
}
Publisher : Full stack programmer stack length , Reprint please indicate the source :https://javaforall.cn/116289.html Link to the original text :https://javaforall.cn
边栏推荐
猜你喜欢
I Basic concepts
Tensorflow2.x下如何运行1.x的代码
Don't fall behind! Simple and easy-to-use low code development to quickly build an intelligent management information system
万字总结数据存储,三大知识点
OneSpin 360 DV新版发布,刷新FPGA形式化验证功能体验
AADL inspector fault tree safety analysis module
CodeSonar通过创新型静态分析增强软件可靠性
Intelligent software analysis platform embold
上海交大最新《标签高效深度分割》研究进展综述,全面阐述无监督、粗监督、不完全监督和噪声监督的深度分割方法
How to meet the dual needs of security and confidentiality of medical devices?
随机推荐
openGl超级宝典学习笔记 (1)第一个三角形「建议收藏」
死锁的产生条件和预防处理[通俗易懂]
使用枚举实现英文转盲文
How to meet the dual needs of security and confidentiality of medical devices?
凌云出海记 | 赛盒&华为云:共助跨境电商行业可持续发展
恶魔奶爸 B2 突破语法,完成正统口语练习
ERROR: 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your
部署、收回和删除解决方式—-STSADM和PowerShell「建议收藏」
阿洛的烦恼
Can Huatai Securities achieve Commission in case of any accident? Is it safe to open an account
[function recursion] do you know all five classic examples of simple recursion?
Static analysis of software defects codesonar 5.2 release
object-c编程tips-timer「建议收藏」
如何挑选基金产品?2022年7月份适合买什么基金?
Is it safe to open an account online now? I want to know where I can open an account in Nanning now?
uva 12230 – Crossing Rivers(概率)「建议收藏」
Codesonar enhances software reliability through innovative static analysis
easyui 日期控件清空值
不落人后!简单好用的低代码开发,快速搭建智慧管理信息系统
ERROR: 1064 (42000): You have an error in your SQL syntax; check the manual that corresponds to your