坐标离散化(离散化 + 稀疏图离散处理)

坐标离散化

 

离散化目的

坐标离散化，实际上就是把较大的稀疏图变得'紧密'一点，让整个图形缩小但是不改变它本身的'结构'其实离散化处理后我们已经不关心每个点的坐标，而是关心这些点或者线之间的关系，比如上述的题目就是让你求区域的个数，当然这种题目在边的长度比较小的时候直接BFS或者DFS就能出来，但是在比较大的稀疏图中，就会不能开那么大的地图数组或者T或者爆栈反正直接想存整个地图的操作不可行(在一定时间内)，这时候就需要用到离散化处坐标，让它变得紧密一点

坐标离散化的思想/原理

将地图中前后没有变化的行列消除后并不影响区域的个数，只要存储有直线的行列和前后的行列就行这样的话地图大小最大\(6n\times6n\)(个人觉得\(3n\times3n\)就足够) tips:上面的题目中的

并不是说经过离散化操作后就会缩小成这样，或者是说不一定是最优的离散化处理结果，但是一样的能进行离散化操作 例题和离散化操作代码

具体的离散化操作分为三部分1. 排序2. 去重(去掉相邻的重复元素)3. 坐标离散化处理(最关键的！！！详情请参见代码) Code：

#include
#include
#include
#include
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 xs;
	//先将所有x坐标放进xs数组中 
	for(int i = 0; i < n; ++i) {
		for(int d = -1; d