hihoCoder 1495-矩形分割

hihoCoder 1495-矩形分割

/\
\/

/\/\
\  /
\/\

输出

3 4
/\/\
\  /
\/\

7

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

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

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

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.