大家好，又见面了，我是全栈君。
链接：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;
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。
发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/116289.html原文链接：https://javaforall.net
