[TC_SRM_466]Drawing Black Crosses 试题描述
\(n \times m\)（\(n, m \le 20\)）的棋盘
此中至多有 \(8\) 个格子为黑色，，其他格子为白色
每次可以选一个白格子把它地址的行、列包孕它自己酿成黑色
求把棋盘全酿成黑色的操纵方案数
输入传给你一个 string[] 类型的参数
输出返回一个整数暗示答案
输入示例 {"B..B", "B.B.", "...B", "BB.B", "...."} 输出示例 Returns 324 数据规模及约定见“试题描述”
题解由于黑格子不赶过 \(8\) 个，并且每次操纵都是整行整列变黑，所以可以任意交换行列，不会影响最终功效。
于是我们可以把它交换成左上角最多 \(8 \times 8\) 区域内有黑格子，剩下一个反 \(L\) 型的全白区域。
对付全白区域，我们只需要关心它有几行几列就行了；而对付有黑格子的处所就需要用状压。
于是令 \(f(s_x, s_y, i, j)\) 暗示对付有黑格子的区域行笼罩的调集是 \(s_x\)，列笼罩调集为 \(s_y\)，全白区域笼罩了 \(i\) 行 \(j\) 列，然后转移显然。
最后累计答案时需要开个数组模拟一下确定哪些状态是最终状态。（仿佛也可以看哪些状态没有后继状态吧，这样快一点，但是我不管了。这题搞了我一个上午，弄得我生活不能自理）
#include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <algorithm> #include <vector> using namespace std; #define rep(i, s, t) for(int i = (s); i <= (t); i++) #define dwn(i, s, t) for(int i = (s); i >= (t); i--) const int maxspace = 12010101, maxn = 21, MOD = 1000000007; #define LL long long int n, m, bn, bm, sn, sm, _x[maxn*maxn], _y[maxn*maxn], cb, xnum[maxn*maxn], ynum[maxn*maxn]; char Map[maxn][maxn]; bool g[maxn][maxn], tg[maxn][maxn]; int F[maxspace]; #define f(si, sj, i, j) F[(si)*(sm+1)*(n-bn+1)*(m-bm+1)+(sj)*(n-bn+1)*(m-bm+1)+(i)*(m-bm+1)+(j)] class DrawingBlackCrosses { public: int count(vector <string> field) { n = field.size(); m = field[0].length(); rep(i, 0, n - 1) strcpy(Map[i], field[i].c_str()); rep(i, 0, n - 1) rep(j, 0, m - 1) if(Map[i][j] == ‘B‘) { _x[cb] = i; _y[cb++] = j; xnum[bn++] = i; ynum[bm++] = j; } sort(xnum, xnum + bn); sort(ynum, ynum + bm); bn = unique(xnum, xnum + bn) - xnum; bm = unique(ynum, ynum + bm) - ynum; sn = (1 << bn) - 1; sm = (1 << bm) - 1; rep(i, 0, cb - 1) { _x[i] = lower_bound(xnum, xnum + bn, _x[i]) - xnum; _y[i] = lower_bound(ynum, ynum + bm, _y[i]) - ynum; g[_x[i]][_y[i]] = 1; } int sx = 0, sy = 0, fullx = 0, fully = 0; // all_black rep(i, 0, n - 1) { bool ab = 1; rep(j, 0, m - 1) if(!g[i][j]){ ab = 0; break; } if(ab && i < bn) sx |= 1 << i; ab = 1; rep(j, 0, bm - 1) if(!g[i][j]){ ab = 0; break; } if(i < bn) fullx |= (int)ab << i; } rep(j, 0, m - 1) { bool ab = 1; rep(i, 0, n - 1) if(!g[i][j]){ ab = 0; break; } if(ab && j < bm) sy |= 1 << j; ab = 1; rep(i, 0, bn - 1) if(!g[i][j]){ ab = 0; break; } if(j < bm) fully |= (int)ab << j; } f(sx, sy, n - bn, m - bm) = 1; rep(si, 0, sn) rep(sj, 0, sm) dwn(i, n - bn, 0) dwn(j, m - bm, 0) if(f(si, sj, i, j)) { int now = f(si, sj, i, j), tsi, tsj, ti, tj; rep(ini, 0, bn) rep(inj, 0, bm) { if(ini < bn) tsi = si | (1 << ini), ti = i; else tsi = si, ti = i - 1; if(inj < bm) tsj = sj | (1 << inj), tj = j; else tsj = sj, tj = j - 1; if(ini < bn && inj < bm && !g[ini][inj] && !(si >> ini & 1) && !(sj >> inj & 1)) (f(tsi, tsj, ti, tj) += now) %= MOD; if(ini < bn && inj == bm && !(si >> ini & 1) && j > 0) (f(tsi, tsj, ti, tj) += (LL)now * j % MOD) %= MOD; if(ini == bn && inj < bm && i > 0 && !(sj >> inj & 1)) (f(tsi, tsj, ti, tj) += (LL)now * i % MOD) %= MOD; if(ini == bn && inj == bm && i > 0 && j > 0) (f(tsi, tsj, ti, tj) += (LL)now * i % MOD * j % MOD) %= MOD; } } int ans = 0; rep(si, 0, sn) rep(sj, 0, sm) rep(i, 0, n - bn) rep(j, 0, m - bm) if(f(si, sj, i, j)) { memcpy(tg, g, sizeof(g)); rep(x, 0, bn - 1) if(si >> x & 1) rep(y, 0, m - 1) tg[x][y] = 1; rep(y, 0, bm - 1) if(sj >> y & 1) rep(x, 0, n - 1) tg[x][y] = 1; dwn(x, n - 1, n - (n - bn - i)) rep(y, 0, m - 1) tg[x][y] = 1; dwn(y, m - 1, m - (m - bm - j)) rep(x, 0, n - 1) tg[x][y] = 1; bool all1 = 1; rep(x, 0, n - 1) rep(y, 0, m - 1) if(!tg[x][y]){ all1 = 0; break; } if(all1) (ans += f(si, sj, i, j)) %= MOD; } return ans; } };