1019 Separate the Animals
Statement
Metadata
- 作者: LIU, Rujia
- 单位: 北京尔宜居科技有限责任公司
- 代码长度限制: 16 KB
- 时间限制: 1500 ms
- 内存限制: 64 MB
There are some animals in a zoo which can be described as a grid with N rows and M columns. Your task is to place some obstacles so that no pairs of animals can reach each other.
Two animals can reach each other if and only if their cells are 4-connected. For example, in Figure 1, the central blue cell can be reached by the four red cells, and cannot be reached by the other four white cells.
Figure 1
What is more, you must put obstacles in exactly K cells, which are 4-connected and form exactly H holes. Here a hole is defined as a 4-connected part with finitely many open cells while the zoo is placed in an infinite open grid. For example, there are 2 holes (the green and the yellow areas) in Figure 2.
Figure 2
For the following grid with two animals:
Figure 3
If K = 8 and H = 1, one way to separate them is the following:
Figure 4
Figure 5 is illegal because it contains no hole.
Figure 5
Figure 6 is also illegal because the obstacles are not 4-connected.
Figure 6
Given some animals, you are supposed to count the number of different solutions.
Input Specification
Each input file contains one test case. For each case, the first line gives four integers: N, M, K, H (2
Then N lines follow, each contains M characters, which are either . or O, representing an open cell or an animal, respectively. There will be at least 2 animals.
Output Specification
For each case, print a single line containing a single integer: the number of solutions.
Sample Input
Sample Output
Solution
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define dbg(x...) \
do { \
cout << "\033[32;1m" << #x << " -> "; \
err(x); \
} while (0)
void err() {
cout << "\033[39;0m" << endl;
}
template <class T, class... Ts>
void err(const T& arg, const Ts&... args) {
cout << arg << ' ';
err(args...);
}
int n, m, K, h;
const int N = 15;
char g[N][N];
int a[N][N], vis[N * N];
inline int id(int x, int y) {
return (x - 1) * m + y;
}
unordered_map<ll, int> mp;
int fa[N * N], sze[N * N];
int find(int x) {
return fa[x] == -1 ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x != y) {
fa[x] = y;
sze[y] += sze[x];
}
}
int Move[][2] = {
-1,
0,
0,
-1,
1,
0,
0,
1,
};
inline bool valid(int x, int y) {
if (x < 1 || x > n || y < 1 || y > m)
return 0;
return 1;
}
inline bool ok(ll sta) {
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int ID = id(i, j);
fa[ID] = -1;
sze[ID] = (g[i][j] != '.');
a[i][j] = ((sta >> ID) & 1);
vis[ID] = a[i][j] ^ 1;
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
if (a[i][j] == 0) {
for (int k = 0; k < 2; ++k) {
int ni = i + Move[k][0];
int nj = j + Move[k][1];
if (valid(ni, nj) && a[ni][nj] == 0) {
merge(id(i, j), id(ni, nj));
if (sze[find(id(i, j))] > 1)
return false;
}
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
if (g[i][j] == 'o') {
if (sze[find(id(i, j))] > 1) {
return false;
}
}
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j)
if (vis[id(i, j)] == 1) {
for (int k = 0; k < 4; ++k) {
int ni = i + Move[k][0];
int nj = j + Move[k][1];
if (!valid(ni, nj)) {
vis[find(id(i, j))] = 0;
vis[id(i, j)] = 0;
break;
}
}
}
}
int cnt = 0;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (fa[id(i, j)] == -1) {
cnt += vis[id(i, j)];
}
}
}
return cnt == h;
}
void bfs() {
int res = 0;
queue<ll> que;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
if (g[i][j] == '.') {
ll x = 1ll << id(i, j);
// dbg(i, j, x);
que.push(x);
mp[x] = 1;
}
}
}
while (!que.empty()) {
ll sta = que.front();
que.pop();
if (__builtin_popcountll(sta) == K) {
// if (ok(sta)) dbg(sta);
// for (int i = 1; i <= n; ++i)
// printf("%s\n", g[i] + 1);
res += ok(sta);
continue;
}
if (__builtin_popcountll(sta) > K)
continue;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
int ID = id(i, j);
if (g[i][j] == '.' && ((sta >> ID) & 1) == 0) {
for (int k = 0; k < 4; ++k) {
int ni = i + Move[k][0];
int nj = j + Move[k][1];
if (valid(ni, nj) && ((sta >> id(ni, nj)) & 1) == 1) {
ll nx = sta ^ (1ll << ID);
if (mp.count(nx) == 0) {
que.push(nx);
mp[nx] = 1;
}
break;
}
}
}
}
}
}
printf("%d\n", res);
}
int main() {
scanf("%d%d%d%d", &n, &m, &K, &h);
for (int i = 1; i <= n; ++i) scanf("%s", g[i] + 1);
bfs();
return 0;
}