AOJ 0531 坐标离散化

一、题目大意

在(0<=x<=w，0<=y<=h)的坐标系里有多个矩形，把区域分成了多个部分，我们需要针对找出被矩形分割的连通的区块数量。

二、解题思路

这个题目其实和学DFS时候那个找出连通的水洼是一样的。只是这个地图比较大，没办法建立那么大的数组，但是矩形的数量也很少，所以考虑使用坐标离散化。

坐标离散化的思路其实也很简单，就是我们把每一个有效坐标k和它 的前一个k-1和后一个坐标k+1都放在一个数组里，然后对这个数组排序加去重（先排序再双指针去重最快），之后用元素k在这个数组里的位置来替换这个元素本身的值，这种离散化对于需要打表的题，比如DP、DFS、BFS比较有效。

本题目给出的是坐标，但是DFS需要用的是区块，所以我就把(x1,y1)到(x2,y2)的矩形看作从[x1,x2-1]到[y1,y2-1]这些坐标中间的区块。那么[0,w-1]的坐标范围，其实真正的放置区块的数量就是[0,w-2]也就是w-1个区块，这个说的其实不清晰，我表达能力确实是太差了。主要的意思就是解释下为什么我把去重后的数量-1作为w和h，因为坐标和区块之间差一个，所以减少一个。

三、代码

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int, int> P;
int x[6007], y[6007], xLen, yLen, w, h, x_1[1007], x_2[1007], y_1[1007], y_2[1007], n, ans;
int dx[] = {1, 0, -1, 0}, dy[] = {0, 1, 0, -1};
bool field[6007][6007];
queue<P> que;
void input()
{ans = 0;scanf("%d", &n);for (int i = 0; i < n; i++){scanf("%d%d%d%d", &x_1[i], &y_1[i], &x_2[i], &y_2[i]);}
}
void compress()
{xLen = 0;for (int i = 0; i < n; i++){if (x_1[i] > 0){x[xLen++] = x_1[i] - 1;}x[xLen++] = x_1[i];if (x_1[i] < w){x[xLen++] = x_1[i] + 1;}if (x_2[i] > 0){x[xLen++] = x_2[i] - 1;}x[xLen++] = x_2[i];if (x_2[i] < w){x[xLen++] = x_2[i] + 1;}}yLen = 0;for (int i = 0; i < n; i++){if (y_1[i] > 0){y[yLen++] = y_1[i] - 1;}y[yLen++] = y_1[i];if (y_1[i] < h){y[yLen++] = y_1[i] + 1;}if (y_2[i] > 0){y[yLen++] = y_2[i] - 1;}y[yLen++] = y_2[i];if (y_2[i] < h){y[yLen++] = y_2[i] + 1;}}sort(x, x + xLen);sort(y, y + yLen);
}
void distinctBy2Posinter()
{int tmpLen = 1;for (int i = 1; i < xLen; i++){if (x[tmpLen - 1] != x[i]){x[tmpLen++] = x[i];}}xLen = tmpLen;tmpLen = 1;for (int i = 1; i < yLen; i++){if (y[tmpLen - 1] != y[i]){y[tmpLen++] = y[i];}}yLen = tmpLen;
}
void handleX_1X_2Y_1Y_2()
{for (int i = 0; i < n; i++){x_1[i] = lower_bound(x, x + xLen, x_1[i]) - x;x_2[i] = lower_bound(x, x + xLen, x_2[i]) - x;y_1[i] = lower_bound(y, y + yLen, y_1[i]) - y;y_2[i] = lower_bound(y, y + yLen, y_2[i]) - y;}w = xLen - 1;h = yLen - 1;
}
void handleField()
{for (int i = 0; i < h; i++){for (int j = 0; j < w; j++){field[i][j] = true;}}for (int i = 0; i < n; i++){for (int j = y_1[i]; j <= (y_2[i] - 1); j++){for (int k = x_1[i]; k <= (x_2[i] - 1); k++){field[j][k] = false;}}}
}
void bfs()
{while (!que.empty()){P p = que.front();que.pop();for (int i = 0; i < 4; i++){int ny = p.first + dy[i];int nx = p.second + dx[i];if (ny >= 0 && ny < h && nx >= 0 && nx < w && field[ny][nx]){field[ny][nx] = false;que.push(P(ny, nx));}}}
}
void solve()
{for (int i = 0; i < h; i++){for (int j = 0; j < w; j++){if (field[i][j]){field[i][j] = false;que.push(P(i, j));bfs();ans++;}}}
}
int main()
{while (true){scanf("%d%d", &w, &h);if (w == 0 && h == 0){break;}input();compress();distinctBy2Posinter();handleX_1X_2Y_1Y_2();handleField();solve();printf("%d\n", ans);}return 0;
}