/*#坐标离散化 (来自《挑战程序设计竞赛》P164) 给出题目和主体代码: 题目: 区域的个数 w*h的格子上画了n条或垂直或水平的宽度为1的直线。求出这些线将格子划分了多少个区域 (w和h的范围都为[1, 1e6],n的范围为[1,500]) 思路: 一般先想到的是类似水塘问题的处理,建立数组并深度优先搜索 但是这个问题中w和h最大为1000000,所以没办法创建w*h的数组。因此我们要使用坐标离散化这一技巧 将前后没有变化的行列(意思是消除后不会影响区域个数的)相除后并不会影响区域的个数 数组里只需要存储有直线的行列以及其前后的行列就足够了,这样的话大小最多3n*3n就足够了,因此就可以创建出数组并利用搜索求出区域的个数 (争议:《挑战》原文是说 6n * 6n,可是我觉得似乎有些不对劲,我特意请教了师兄和队友以后,他们也觉得是3n*3n) 收获: 1. 坐标压缩 2. find函数可以在vector中找到某个元素的位置 注意,find函数要求支持 == ,所以如果是自定义类型,需要先重载 == blog: http://www.cnblogs.com/fnlingnzb-learner/p/5889026.html 3. 区域很大时,用递归函数可能栈溢出,故而此题改用队列 4. unique函数和erase函数 有关blog: http://www.cnblogs.com/zhangshu/archive/2011/07/23/2115090.html http://www.cnblogs.com/liyazhou/archive/2010/02/07/1665421.html 注意: unique的去重并非真正的去重,只是将重复的元素都排到后面去。此外,unique只能在相邻元素中去重,所以使用之前应该先排序 *****技巧:真正的去重并删除重复部分**** vector<int> v; sort(v.begin(), v.end()); v.erase(unique( v.begin(), v.end() ), v.end()); */
int W, H, N; int X1[MAX_N], X2[MAX_N], Y1[MAX_N], Y2[MAX_N]; bool fld[MAX_N * 3][MAX_N * 3] int dx[4] = {0, 0, -1, 1}; int dy[4] = {-1, 1, 0, 0}; // 对 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) xs.push_back(tx1); if (tx2 >= 1 && tx2 <= w) xs.push_back(tx2); } } sort(xs.begin(), xs.end()); 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(); x2[i] = find(xs.begin(), xs.end(), x2[i]) - xs.begin(); } return xs.size(); } /*这个函数对坐标进行了压缩: 1. 将坐标的值变成了“这是第几种坐标”(种类和区域个数有关,同个区域的就是同一种坐标),函数返回值是一共有多少种坐标 2. 起止行(列)的前后行(列)若在 w*w 的范围内,则压栈(其实是压入队列)其前后行(列),因为每个黑行对数区域的影响,也就只有它的前后行和本身那行,对别的行是不会有影响的 */ void solve() { // 坐标离散化 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++; // 宽度优先搜索 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 || tx >= W || ty < 0 || ty >= H) continue; if (fld[ty][tx]) continue; que.push(make_pair(tx, ty)); fld[ty][tx] = true; } } } cout << ans << endl; }