1 条题解

  • 0
    @ 2026-1-12 22:22:40

    #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
    上传者