hihoCoder 1495-矩形分割

hihoCoder 1495-矩形分割

#1495 : 矩形分割

时间限制:10000ms
单点时限:1000ms
内存限制:256MB

描述

小Hi有一块由NxM个单位正方形组成的矩形。现在小Ho在某些单位正方形上画了一道分割线,这条分割线或者是单位正方形的主对角线(用'\'表示),或者是副对角线(用'/'表示)。

现在小Hi想知道这些分割线把NxM的矩形分割成了多少块区域。

例如

/\
\/

就把2x2的矩形分成了5个区域。

/\/\
\  /
 \/\

把3x4的矩形分成了7个区域。

输入

第一包含两个整数N和M。(1 <= N, M <= 100)

以下N行每行包含M个字符。每个字符只可能是/\或者空格。

输出

分割成的区域数目。

样例输入
3 4    
/\/\  
\  /  
 \/\
样例输出
7

本题又是一个考察并查集的题,再一次栽在了并查集!

给定一个由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读取上一行的换行符。

#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;
}

本代码提交AC,用时4MS。

Leave a Reply

Your email address will not be published. Required fields are marked *