自动搬运

查看原文

来自洛谷，原作者为

	zhylj 人生输家

搬运于2025-08-24 22:25:44，当前版本为作者最后更新于2022-01-12 18:05:37，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑暴搜每个位置放哪个拼图，然后 $\mathcal O(wh)$ Check，注意到由于题目的限制，角落上的拼图的位置是确定的；而边界上的拼图被确定在 $n-2$ 个位置里，可以在内部枚举选择方案；剩下的位置再暴搜。这样情况就只剩下了 $(n-2)!^4((n-2)^2)!$ 种，非常之少，随便实现就可以过了。

const int N = 50;

int k, w, h, n, W, H;
char str[N][N][N], ans[N][N];

void Output() {
	printf("%d %d\n", W, H);
	for(int i = 1; i <= H; ++i)
		printf("%s\n", ans[i] + 1);
}

bool Repl(int id, int pos_x, int pos_y, char c_bg, char c_ed) {
	std::vector <pii> vaild_pos;
	int mov_x = -h + (pos_x - 1) * h + 1, mov_y = -w + (pos_y - 1) * w + 1;
	bool up_b = true, dn_b = true, lf_b = true, ri_b = true;
	for(int y = w; y <= 2 * w - 1; ++y) {
		if(str[id][h - 1][y] != '.' || str[id][h][y] == '.') up_b = false;
		if(str[id][2 * h][y] != '.' || str[id][2 * h - 1][y] == '.') dn_b = false;
	}
	for(int x = h; x <= 2 * h - 1; ++x) {
		if(str[id][x][w - 1] != '.' || str[id][x][w] == '.') lf_b = false;
		if(str[id][x][2 * w] != '.' || str[id][x][2 * w - 1] == '.') ri_b = false;
	}
	if((up_b && pos_x != 1) || (dn_b && pos_x != n) ||
		(lf_b && pos_y != 1) || (ri_b && pos_y != n)) return false;
	for(int x = 1; x <= h * 3 - 2; ++x)
		for(int y = 1; y <= w * 3 - 2; ++y) {
			int nx = x + mov_x, ny = y + mov_y;
			if(str[id][x][y] != '.') {
				if(nx <= 0 || ny <= 0 || nx > H || ny > W || ans[nx][ny] != c_bg)
					return false;
				vaild_pos.push_back(mkp(nx, ny));
			}
		}
	for(pii i : vaild_pos) {
		int x = i.fi, y = i.se;
		ans[x][y] = c_ed;
	}
	return true;
}

bool vis[N];
void Dfs(int cur_pos_x, int cur_pos_y) {
	if(cur_pos_x == n + 1) { Output(); exit(0); }
	for(int i = 1; i <= k; ++i) {
		if(!vis[i] && Repl(i, cur_pos_x, cur_pos_y, '.', i - 1 + 'A')) {
			vis[i] = true;
			Dfs(cur_pos_x + (cur_pos_y == n), cur_pos_y % n + 1);
			Repl(i, cur_pos_x, cur_pos_y, i - 1 + 'A', '.');
			vis[i] = false;
		}
	}
}

int main() {
	rd(k, w, h);
	n = lround(floor(sqrt(k)));
	W = w * n; H = h * n;
	for(int i = 1; i <= H; ++i)
		for(int j = 1; j <= W; ++j) ans[i][j] = '.';
	for(int i = 1; i <= k; ++i)
		for(int j = 1; j <= h * 3 - 2; ++j)
			scanf("%s", str[i][j] + 1);
	Dfs(1, 1);
	return 0;
}