坐标离散化

 

离散化目的

坐标离散化，实际上就是把较大的稀疏图变得’紧密’一点，让整个图形缩小但是不改变它本身的’结构’
 
其实离散化处理后我们已经不关心每个点的坐标，而是关心这些点或者线之间的关系，比如上述的题目
 
就是让你求区域的个数，当然这种题目在边的长度比较小的时候直接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 compressint *x1,int *x2,int w) {
	vector<int> xs;
	//先将所有x坐标放进xs数组中 
	forint i = 0; i < n; ++i) {
		forint d = -1; d <= 1; ++d) {
			int tx1 = x1[i] + d;
			int tx2 = x2[i] + d;
			if1 <= tx1 && tx1 <= w)	xs.push_backtx1);
			if1 <= tx2 && tx2 <= w)	xs.push_backtx2);
		}
	}
	//1.排序 
	sortxs.begin),xs.end)); 
	//2.去重    因为unique函数返回值是去掉相邻重复元素后的尾部的位置
	//			他会把重复的元素添加到尾部，所以元素的个数还是没变) 
	xs.eraseuniquexs.begin),xs.end))),xs.end)); 
	//3.离散化，将大空间的下标投射到小范围中 
	forint i = 0; i < n; ++i) {
		x1[i] = findxs.begin),xs.end),x1[i]) - xs.begin);//当然这里也可以自己写一个二分函数 
		x2[i] = findxs.begin),xs.end),x2[i]) - xs.begin);//貌似更快 
	}
	return xs.size);//返回的是离散后的宽或者长 
}
void bfsint x,int y) {
	queue<Node> que;
	que.push{x,y});
	mp[x][y] = true;
	while!que.empty)) {
		Node t = que.front);
		que.pop);
		forint i = 0; i < 4; ++i) {
			int nx = t.x + dx[i];
			int ny = t.y + dy[i];
			ifnx >= 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);
	forint i = 0;i < n; ++i)	scanf"%d",&X1[i]);
	forint i = 0;i < n; ++i)	scanf"%d",&X2[i]);
	forint i = 0;i < n; ++i)	scanf"%d",&Y1[i]);
	forint i = 0;i < n; ++i)	scanf"%d",&Y2[i]);
	
	W = compressX1,X2,W);//列数 
	H = compressY1,Y2,H);//行数 
	//绘制地图 
	forint i = 0; i < n; ++i) {
		forint y = Y1[i]; y <= Y2[i]; ++y) {
			forint x = X1[i]; x <= X2[i]; ++x) {
				mp[y][x] = true; 
			}
		}
	}
		forint y = 0; y < H; ++y) {
			forint x = 0; x < W; ++x) {
				printf"%d%c",mp[y][x],x==W-1?'
':' '); 
			}
		}
	int ans = 0;
	forint i = 0; i < H; ++i) {
		forint j = 0; j < W; ++j) {
			if!mp[i][j]) {
				ans++;
				bfsi,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