1 条题解
-
0

#include <bits/stdc++.h> #define popc __builtin_popcount #define ctz __builtin_ctz using std::cin; using std::cout; typedef unsigned int u32; int n, R, C; int g[4][4]; char s[100]; char mat[100][100]; int hor[16][16], ver[16][16]; u32 can[4][4]; bool avai[16]; struct puzzle { u32 buf[13], *p; bool Lb, Rb, Ub, Db; friend std::istream & operator >> (std::istream &in, puzzle &B) { int i, j; B.p = B.buf + R - 1; for (i = 0; i < 3 * R - 2; ++i) { in >> s, B.buf[i] = 0; for (j = 0; j < 3 * C - 2; ++j) B.buf[i] |= u32(s[j] != 46) << j; } return in; } void calc_boundary() { int i; u32 S = 0, T = 0, flat_row = ~(-1 << C) << (C - 1); for (i = 0; i < R - 1; ++i) S |= p[~i], T |= p[R + i]; Ub = !S && *p == flat_row, Db = !T && p[R - 1] == flat_row; for (S = 0, T = -1, i = 0; i < R; ++i) S |= p[i], T &= p[i]; Lb = !(S & ~(-1 << (C - 1))) && T >> (C - 1) & 1, Rb = !(S & (-1 << (2 * C - 1))) && T >> 2 * (C - 1) & 1; } } a[16]; bool check_and_print() { int i, u, v, r, c, fr, fc; u32 S, mask = 0; for (i = 0; i < n * R; ++i) memset(mat, 0, sizeof mat); for (r = 0; r < n; ++r) for (c = 0; c < n; ++c) { i = g[r][c]; if (mask >> i & 1) return false; mask |= 1 << i; for (u = 1 - R; u < 2 * R - 1; ++u) for (S = a[i].p[u]; S; S &= S - 1) { v = ctz(S) - (C - 1), fr = r * R + u, fc = c * C + v; if ((u32)fr >= (u32)n * R || (u32)fc >= (u32)n * C || mat[fr][fc]) return false; mat[fr][fc] = 65 + i; } } for (i = 0; i < n * R; ++i) cout << mat[i] << '\n'; return true; } bool check_horizontal(const puzzle &L, const puzzle &R) { int i; if (L.Rb || R.Lb) return false; for (i = 0; i < ::R; ++i) if (L.p[i] & R.p[i] << C) return false; return true; } bool check_vertical(const puzzle &U, const puzzle &D) { int i, j, u[5] = {0}; u32 S; if (U.Db || D.Ub) return false; for (i = 0; i < 2 * R - 1; ++i) for (S = U.p[i]; S; S &= S - 1) if (u32(j = ctz(S) - (C - 1)) < (u32)C) u[j] |= 1 << i; for (i = R - 1; i > -R; --i) for (S = D.p[i]; S; S &= S - 1) if (u32(j = ctz(S) - (C - 1)) < (u32)C) if (u[j] >> (i + R) & 1) return false; return true; } inline void update(int r, int c) { if ((u32)r >= (u32)n || (u32)c >= (u32)n || ~g[r][c]) return; for (int i = 0; i < n * n; ++i) if (can[r][c] >> i & 1) if ((c && ~g[r][c - 1] && !hor[ g[r][c - 1] ][i]) || (c < n - 1 && ~g[r][c + 1] && !hor[i][ g[r][c + 1] ]) || (r && ~g[r - 1][c] && !ver[ g[r - 1][c] ][i]) || (r < n - 1 && ~g[r + 1][c] && !ver[i][ g[r + 1][c] ])) can[r][c] &= ~(1 << i); } bool dfs(u32 mask) { static int stamp = 0; int i, j = 1, r, c, best = INT_MAX; u32 S, T, _can[4][4]; // fprintf(stderr, "dfs [time = %d] (current mask = %u, c = %d)\n", ++stamp, mask, popc(mask)); if (!mask) return check_and_print(); for (r = 0; r < n; ++r) for (c = 0; c < n; ++c) if (!~g[r][c] && popc(can[r][c]) < best) best = popc(can[r][c]), j = r * n + c; if (assert(~j), !best) return false; r = j / n, c = j % n, mask &= ~(1 << j), memcpy(_can, can, 64); for (S = can[r][c]; S; S &= S - 1) { g[r][c] = ctz(S), T = ~(S & -S); for (i = 0; i < 4; ++i) for (j = 0; j < 4; ++j) can[i][j] = _can[i][j] & T; update(r, c - 1), update(r - 1, c), update(r, c + 1), update(r + 1, c); if (dfs(mask)) return true; } return g[r][c] = -1, memcpy(can, _can, 64), false; } int main() { int i, j; u32 LL = 0, RR = 0, UU = 0, DD = 0, ALL = 0; std::ios::sync_with_stdio(false), cin.tie(NULL); cin >> n >> C >> R, n = sqrt(n); cout << n * C << ' ' << n * R << '\n'; if (n == 1) { memset(s, 65, n * C); for (i = 0; i < n * R; ++i) cout << s << '\n'; return 0; } memset(g, -1, sizeof g); for (i = 0; i < n * n; ++i) { cin >> a[i], a[i].calc_boundary(); assert(a[i].Lb + a[i].Rb + a[i].Ub + a[i].Db < 3); if (a[i].Lb && a[i].Ub) assert(!~g[0][0]), g[0][0] = i; else if (a[i].Rb && a[i].Ub) assert(!~g[0][n - 1]), g[0][n - 1] = i; else if (a[i].Lb && a[i].Db) assert(!~g[n - 1][0]), g[n - 1][0] = i; else if (a[i].Rb && a[i].Db) assert(!~g[n - 1][n - 1]), g[n - 1][n - 1] = i; else avai[i] = true; } assert(~g[0][0] && ~g[0][n - 1] && ~g[n - 1][0] && ~g[n - 1][n - 1]); for (i = 0; i < n * n; ++i) for (j = 0; j < n * n; ++j) if (i != j) hor[i][j] = check_horizontal(a[i], a[j]), ver[i][j] = check_vertical(a[i], a[j]); for (i = 0; i < n * n; ++i) if (avai[i]) { ALL |= 1 << i; if (a[i].Lb) LL |= 1 << i; else if (a[i].Rb) RR |= 1 << i; else if (a[i].Ub) UU |= 1 << i; else if (a[i].Db) DD |= 1 << i; } for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) can[i][j] = !j ? LL : j == n - 1 ? RR : !i ? UU : i == n - 1 ? DD : ALL, update(i, j); dfs(~(-1 << (n * n - 1) | 1 << n * (n - 1) | 1 << (n - 1) | 1)); return 0; }
- 1
信息
- ID
- 5706
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者