参考博客
https://www.wxzuir.moe/pat-顶级1019-separate-the-animals-题解/
主要就是状态可以用long long 保存，这样才不超时，开始用set表示状态中有两个点超时
#include<iostream> #include<cstring> #include<queue> #include<set> typedef long long LL; using namespace std; int dr[] = { 1,-1,0,0 }, dl[] = { 0,0,1,-1 }, G[7][7], T[7][7]; int N, M, K, H, f, ans; set<LL> P; int place(int x, int y) { if (x >= 0 && x < N &&y >= 0 && y < M) { if (x == 0 || x == N - 1 || y == 0 || y == M - 1) return 1; else return 2; } return 0; } bool _ok(LL s) { int flag, h = 0, cnt = 0, t = 0, o; memcpy(T, G, sizeof(G)); while (s) { if (s & 1) T[t / M][t%M] = 2;//放置障碍 ++t, s >>= 1; } for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) { if (T[i][j] == 2) continue; queue<int> que; que.push(i*M + j); o = T[i][j]; flag = place(i, j) == 1 ? 1 : 0; T[i][j] = 2; while (!que.empty()) { int r = que.front() / M, l = que.front() % M; que.pop(); for (int i = 0; i < 4; ++i) { int nr = r + dr[i], nl = l + dl[i]; if ((f = place(nr, nl)) && T[nr][nl] != 2) { if (T[nr][nl] == 1) ++o; if (f == 1) flag = 1; T[nr][nl] = 2; que.push(nr*M + nl); } } if (o > 1) return false; } if (flag == 0) ++h; } if (h != H) return false; return true; } void dfs(LL s, int step) { if (P.count(s)) return; P.insert(s); if (step == 0) { if (_ok(s)) ++ans; return; } LL temp = s; int t = 0; while (temp) { if (temp & 1) { int r = t / M, l = t % M; for (int i = 0; i < 4; ++i) { int nr = r + dr[i], nl = l + dl[i]; if (place(nr, nl) && G[nr][nl] == 0 && !(s >> (nr*M + nl) & 1)) dfs((s | (1LL << (nr*M + nl))), step - 1); } } ++t, temp >>= 1; } } int main() { cin >> N >> M >> K >> H; getchar(); for (int i = 0; i < N; ++i) for (int j = 0; j <= M; ++j) G[i][j] = getchar() == '.' ? 0 : 1; for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) if (G[i][j] == 0) dfs(1LL << (i*M + j), K - 1); cout << ans << endl; }