hihoCoder 1495-矩形分割

---

本题又是一个考察并查集的题，再一次栽在了并查集！ 给定一个由n*m个小正方形组成的大矩形，现在在某些小正方形上画一道分隔线，该分隔线可能是小正方形的主对角线\，也可能是副对角线/。问经过分隔之后，把大矩形分隔成了多少块区域。 判断平面区域个数问题，一般都可以转化为并查集的问题，但是这题相对上一次的并查集又进了一步，这题应该算是三维的并查集了。 对于小正方形的每个点，我们用三维信息来表示(x,y,z)，其中x,y表示顶点所在小正方形的行号和列号，z表示该顶点在该小正方形中的位置，坐标从左上角开始顺时针递增，如下图。

0-----1
|     |
|     |
3-----2

初始时，每个顶点自成一体，所以par[i]=i。 但是因为画的分隔线只能是对角线，所以相邻两个正方形中的共享边肯定属于同一个区域，应该把相邻正方形共享边的两个顶点union起来。比如下图中，第一列的两个正方形，蓝色的两条边应该union，即左上角正方形的2号节点应该和左下角正方形的0号节点union；同理，第一行的两个正方形，红色的两条边也应该union，即左上角的1号节点和右上角的3号节点union。 其实，红色的边也可以union 0和2，但此时蓝色的边就应该union 1和3了，只要两者不一致并在整个程序中统一就行。

0-----1  0-----1
|     |  |     |
|     |  |     |
3-----2  3-----2
0-----1
|     |
|     |
3-----2

注意，不是把红色边的0和1 union，2和3 union，因为0和1可能属于不同的区域，比如下图中，红色的0和1就属于不同的区域了。

0-----1  0-----1
|   / |  | \   |
| /   |  |   \ |
3-----2  3-----2
0-----1
|     |
|     |
3-----2

初始化完成之后，就需要进行并查集操作了。如果遇到空格，好说，把这个正方形的四个顶点都union起来。 如果遇到左斜杠/，类似于上图左上角的分隔线，则把这个正方形中的四个顶点分成了两个不同的区域。此时，我们需要统一一个划分顶点的规则：被分隔的对角点和其顺时针的下一个顶点属于一个集合。比如3顺时针的下一个顶点是0，所以3和0 union；1顺时针的下一个顶点是2，所以1和2 union。 类似的，如果遇到右斜杠\，类似上图右上角的分隔线。根据统一的规则，0和1 union，2和3 union。 所有操作完成之后，统计一下并查集中不同区域的个数就是最终结果。 代码如下，注意%c会读取换行符，所以在每行开头先%c读取上一行的换行符。 [cpp] #include<iostream> #include<cstdio> #include<unordered_map> #include<algorithm> #include<functional> #include<vector> using namespace std; const int MAXN = 105; int n, m; vector<int> par(MAXN * MAXN * 4); int find_par(int u) { if (par[u] != u) par[u] = find_par(par[u]); return par[u]; } void union_par(int u, int v) { par[find_par(u)] = find_par(v); } int id(int x, int y, int z) { return x * m * 4 + y * 4 + z; } int main() { //freopen("input.txt", "r", stdin); scanf("%d %d", &n, &m); int total = n * m * 4; for (int i = 0; i < total; ++i)par[i] = i; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { if (i > 0)union_par(id(i, j, 0), id(i – 1, j, 2)); if (j > 0)union_par(id(i, j, 3), id(i, j – 1, 1)); //if (i < n – 1)union_par(id(i, j, 2), id(i + 1, j, 0)); // 多余 //if (j < m – 1)union_par(id(i, j, 1), id(i, j + 1, 3)); // 多余 } } char c; for (int i = 0; i < n; ++i) { scanf("%c", &c); // 读取上一行的\n for (int j = 0; j < m; ++j) { scanf("%c", &c); if (c == ‘ ‘) { union_par(id(i, j, 0), id(i, j, 1)); union_par(id(i, j, 1), id(i, j, 2)); union_par(id(i, j, 2), id(i, j, 3)); //union_par(id(i, j, 3), id(i, j, 0)); // 多余 } else if (c == ‘/’) { union_par(id(i, j, 3), id(i, j, 0)); union_par(id(i, j, 1), id(i, j, 2)); } else if (c == ‘\\’) { union_par(id(i, j, 0), id(i, j, 1)); union_par(id(i, j, 2), id(i, j, 3)); } } } int ans = 0; for (int i = 0; i < total; ++i) { if (find_par(i) == i)++ans; } printf("%d\n", ans); return 0; } [/cpp] 本代码提交AC，用时4MS。]]>