算法
(暴力枚举)
虽然在 $8 \times 8$ 的网格中给 $8$ 个方格染色的方案数为 $_{64}C_{8} = 4426165368$,显然会超时,但我们可以注意到样例3
,能组成 $K$ 格多米诺的方案数一定很少。所以我们暴搜就行了。
C++ 代码
#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (n); ++i)
using std::cin;
using std::cout;
using std::vector;
using std::string;
using vs = vector<string>;
const int di[] = {-1, 0, 1, 0};
const int dj[] = {0, -1, 0, 1};
int n, k;
int ans;
void dfs(vs s) {
int cnt = 0;
rep(i, n)rep(j, n) if (s[i][j] == 'o') ++cnt;
if (cnt == k) {
++ans;
return;
}
rep(i, n)rep(j, n) {
if (s[i][j] != '.') continue;
if (cnt != 0) {
bool ok = false;
rep(v, 4) {
int ni = i + di[v], nj = j + dj[v];
if (ni < 0 or nj < 0 or ni >= n or nj >= n) continue;
if (s[ni][nj] == 'o') ok = true;
}
if (!ok) continue;
}
s[i][j] = 'o';
dfs(s);
s[i][j] = '#';
dfs(s);
return;
}
}
int main() {
cin >> n >> k;
vs s(n);
rep(i, n) cin >> s[i];
dfs(s);
cout << ans << '\n';
return 0;
}
巨巨 为什么这道题的搜索顺序 是两重for?
看题hh
正常搜索连通块 不都从当前那个点开始。。
从哪个点开始没关系的,深搜每次遍历结束会把搜过的标记好
这道题情景有点不一样,你说的可能是已连通的,但是题目要求是染色后连通