坐标离散化
离散化目的
坐标离散化，实际上就是把较大的稀疏图变得'紧密'一点，让整个图形缩小但是不改变它本身的'结构'
其实离散化处理后我们已经不关心每个点的坐标，而是关心这些点或者线之间的关系，比如上述的题目
就是让你求区域的个数，当然这种题目在边的长度比较小的时候直接BFS或者DFS就能出来，但是在比较
大的稀疏图中，就会不能开那么大的地图数组或者T或者爆栈反正直接想存整个地图的操作不可行(在一
定时间内)，这时候就需要用到离散化处坐标，让它变得紧密一点
坐标离散化的思想/原理
将地图中前后没有变化的行列消除后并不影响区域的个数，只要存储有直线的行列和前后的行列就行
这样的话地图大小最大(6n imes6n)(个人觉得(3n imes3n)就足够)
tips:上面的题目中的
并不是说经过离散化操作后就会缩小成这样，或者是说不一定是最优的离散化处理结果，但是一样的能进行离散化操作
例题和离散化操作代码
具体的离散化操作分为三部分
1. 排序
2. 去重(去掉相邻的重复元素)
3. 坐标离散化处理(最关键的！！！详情请参见代码)
Code：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
struct Node{
int x,y;
};
const int N = 505;
bool mp[N * 6][N * 6];
int dx[4] = {-1,1,0,0},dy[4] = {0,0,-1,1};
int X1[N * 6],Y1[N * 6],X2[N * 6],Y2[N * 6];
int W,H,n;
//对x1和x2进行离散化处理，并且返回离散后的宽度
int compress(int *x1,int *x2,int w) {
vector<int> xs;
//先将所有x坐标放进xs数组中
for(int i = 0; i < n; ++i) {
for(int d = -1; d <= 1; ++d) {
int tx1 = x1[i] + d;
int tx2 = x2[i] + d;
if(1 <= tx1 && tx1 <= w) xs.push_back(tx1);
if(1 <= tx2 && tx2 <= w) xs.push_back(tx2);
}
}
//1.排序
sort(xs.begin(),xs.end());
//2.去重 因为unique函数返回值是去掉相邻重复元素后的尾部的位置
// (他会把重复的元素添加到尾部，所以元素的个数还是没变)
xs.erase((unique(xs.begin(),xs.end())),xs.end());
//3.离散化，将大空间的下标投射到小范围中
for(int i = 0; i < n; ++i) {
x1[i] = find(xs.begin(),xs.end(),x1[i]) - xs.begin();//当然这里也可以自己写一个二分函数
x2[i] = find(xs.begin(),xs.end(),x2[i]) - xs.begin();//貌似更快
}
return xs.size();//返回的是离散后的宽或者长
}
void bfs(int x,int y) {
queue<Node> que;
que.push({x,y});
mp[x][y] = true;
while(!que.empty()) {
Node t = que.front();
que.pop();
for(int i = 0; i < 4; ++i) {
int nx = t.x + dx[i];
int ny = t.y + dy[i];
if(nx >= 0 && nx < H && ny >= 0 && ny < W && (!mp[nx][ny])) {
que.push({nx,ny});
mp[nx][ny] = true;
}
}
}
}
int main()
{
scanf("%d%d%d",&W,&H,&n);
for(int i = 0;i < n; ++i) scanf("%d",&X1[i]);
for(int i = 0;i < n; ++i) scanf("%d",&X2[i]);
for(int i = 0;i < n; ++i) scanf("%d",&Y1[i]);
for(int i = 0;i < n; ++i) scanf("%d",&Y2[i]);
W = compress(X1,X2,W);//列数
H = compress(Y1,Y2,H);//行数
//绘制地图
for(int i = 0; i < n; ++i) {
for(int y = Y1[i]; y <= Y2[i]; ++y) {
for(int x = X1[i]; x <= X2[i]; ++x) {
mp[y][x] = true;
}
}
}
for(int y = 0; y < H; ++y) {
for(int x = 0; x < W; ++x) {
printf("%d%c",mp[y][x],x==W-1?'
':' ');
}
}
int ans = 0;
for(int i = 0; i < H; ++i) {
for(int j = 0; j < W; ++j) {
if(!mp[i][j]) {
ans++;
bfs(i,j);
}
}
}
printf("%d
",ans);
return 0;
/*
10 10 5
1 1 4 9 10
6 10 4 9 10
4 8 1 1 6
4 8 10 5 10
*/
}
以后有用到的时候再更新hh