算法
(bit全探索、并查集) $O(2^{16})$
本题不需要搜索护城河,我们可以用 $2^{16}$ 种方式来搜索护城河内部的方格!若护城河内部没有覆盖所有的村子,则显然不能建成。 此外,我们还需在护城河周围再加一个方块变成 $6 \times 6$ 的区域,然后利用并查集来维护所有方格的连通性,即把处于同一种状态的方格合并。若最后的连通分量个数是 $2$,则表示可以建成。
注意:连通分量中不能出现以下这三种形状
C++ 代码
#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::min;
using std::vector;
int main() {
int n = 6, m = 4;
int a = 0;
rep(i, m)rep(j, m) {
int ni = i*m+j;
int na;
cin >> na;
a |= na << ni;
}
int ans = 0;
rep(s, 1<<16) if ((s&a) == a) {
dsu d(n * n);
vector x(n, vector<int>(n));
rep(i, m)rep(j, m) if (s>>(i*m+j)&1) x[i+1][j+1] = 1;
rep(i, n)rep(j, n) {
int ni = i*n+j;
if (i+1 < n and x[i][j] == x[i+1][j]) d.merge(ni, ni+n);
if (j+1 < n and x[i][j] == x[i][j+1]) d.merge(ni, ni+1);
}
int cnt = 0;
rep(i, n*n) if (d.leader(i) == i) cnt++;
if (cnt == 2) ++ans;
}
cout << ans << '\n';
return 0;
}