3.2.5 二维坐标离散化

坐标离散化"/>

3.2.5 二维坐标离散化

离散化针对于：点的个数很少，但数据范围很大的情况。比如本题给出了1e6的数据范围，如果以“桶”的思想以数组计数，那么，第一二维数组没办法开那么大，第二如果用别的容器实现，因为过于稀疏，十分浪费空间。
离散化的核心在于映射，但是我们不能仅仅根据个数无脑映射，而要考虑到所求问题的限制，以保证我们构造的映射不影响目标问题的解答。在这个过程中会涉及到相同合并、不相邻间隔的问题。

以这道题目为例，其实我们离散化主要有两个作用：

• 对于过大的数据，缩小数据范围（Compress函数内sort之后的find()-begin()，其实就是以其在数组中的标号替代其新坐标，完成了减小规模的映射）
• 在缩小数据范围的前提下，进一步简化问题。因为我们要求的是区域的个数，所以实际的面积、长度及其间的比例并不影响问题的求解。在这道题目中，压入Compress内的xs容器之前，进行了对每个坐标(-1, 0, +1)的操作，这一组操作其实是为了合并相同行列。在下图的例子中，第1-3列其实是一样的，我们删去两列只保留1列不会影响问题的解答。通过-1，0， 1的试探，我们其实是人为构造了重复的元素（如果相邻且相同，就会被重复压入xs），之后再借助unique去重，就完成了相同行列的合并简化，对于一些极端情况大大提高了解决问题的效率。
  
  Tips： 注意边界值，决定好地图0/1开始之后后面都要与之对应。如果行列都从1开始，那么Compress中的判定就是>=1；如果是0，就是>=0。

离散化其他注意情况&相关题目

• POJ2528 离散化时要注意根据题意，对相邻情况进行区分，这道题就需要对相邻不相邻做区分。（如果不相邻，就插入一个数字）

#define _CRT_SECURE_NO_WARNINGS
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cstring>using namespace std;/**Test Data::
Standard Input
10 10 5
1 6 4 4
1 10 8 8
4 4 1 10
9 9 1 5
10 10 6 10Standard Output
6
**/#define MAX_N 510
int W, H, N;//W*H的坐标纸，N个线段
int X1[MAX_N], X2[MAX_N], //我们这里用X1, X2存的是坐标，不是“桶”存数目Y1[MAX_N], Y2[MAX_N];
int dx[4] = { 0, 0, -1, 1 },dy[4] = { -1, 1, 0, 0 };//宽搜时寻找上下左右的空白格子
bool fld[MAX_N * 6][MAX_N * 6];//填充用//对x1, x2进行坐标离散化，返回离散化之后的宽度
int compress(int* x1, int* x2, int w)
{vector<int> xs;for (int i = 0; i < N; i++){for (int d = -1; d <= 1; d++){int tx1 = x1[i] + d,tx2 = x2[i] + d;if (tx1 >= 1 && tx1 <= w)//<=线段条数是否因为，只统计区域不用管面积比例的改变所以一定可以在条数之内搞定？（可以缩成1）xs.push_back(tx1);if (tx2 >= 1 && tx2 <= w)xs.push_back(tx2);}}sort(xs.begin(), xs.end());printf("%d\n", xs.end() - xs.begin());xs.erase(unique(xs.begin(), xs.end()), xs.end());for (int i = 0; i < N; i++){x1[i] = find(xs.begin(), xs.end(), x1[i]) - xs.begin();//find()返回指针x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin();}return xs.size();
}int main()
{scanf("%d %d %d", &W, &H, &N);for (int i = 0; i < N; i++)scanf("%d %d %d %d", &X1[i], &X2[i], &Y1[i], &Y2[i]);//坐标离散化W = compress(X1, X2, W);H = compress(Y1, Y2, H);memset(fld, 0, sizeof(fld));//最初都是白格子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++)//线段部分涂黑{fld[y][x] = true;}}}//求区域的个数int ans = 0;for (int y = 0; y < H; y++){for (int x = 0; x < W; x++){if (fld[y][x])continue;ans++;//一旦找到一个白色，就会把周围一片都搞完，所以ans不会搜重，记录的就是白色区域的数目//宽度优先搜索queue<pair<int, int> > que;que.push(make_pair(x, y));while (!que.empty()){int sx = que.front().first, sy = que.front().second;que.pop();for (int i = 0; i < 4; i++)//向空白格子的上下左右四个方向找{int tx = sx + dx[i], ty = sy + dy[i];if (tx < 0 || W <= tx || ty < 0 || H <= ty)//越界退出continue;if (fld[ty][tx])//是黑格子退出continue;que.push(make_pair(tx, ty));//是白格子压入队列，继续宽搜fld[ty][tx] = true;//搜过标记为1避免重复}}}}printf("%d\n", ans);return 0;
}