自动搬运

查看原文

来自洛谷，原作者为

	Rindong 蒟蒻ACMer/GXCPC金/蓝桥B组国一

搬运于2025-08-24 23:03:46，当前版本为作者最后更新于2025-03-04 16:42:10，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

前置知识：精确覆盖问题

精确覆盖问题简单来说就是，给定 $n$ 行 $m$ 列的 01 矩阵，选出若干行使得对于选出的行中，对于第 $j \in [1, m]$ 列有且仅有某一行的第 $j$ 列为 1 。

舞蹈链是一种解决精确覆盖问题的实现方法，在实际应用中，我们通常把行当做选择，列当做限制。也就是说，我们有 $n$ 种选择，$m$ 条需要满足的限制。

本题思路

首先统计出值为 1 的格子数量 $m$，我们让 $k = m + 4$ 其中 $[1, m]$ 列为所有 1 的格子下标（因为每个值为 1 的格子属于 1 个或 0 个图形），$[m + 1, k]$ 列为 4 个图形的下标（因为题目要求我们找出）。

然后枚举每个值为 1 的格子，查看如果以当前格子为起点，是否能摆出某个图形，如果可以，就把这个图案涉及到的几个格子都插入，再插入这个图形的列。否则，只插入当前格子自己的列。

建模完成后，我们使用舞蹈链模板求解即可。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 55, M = 500000;
struct Pos {
	int x, y;
};
char arr[N][N];
int idle = 0;
int L[M], R[M], U[M], D[M], head[M];
int cnt[N * N];
Pos pos[M];
int n, m;
int dir[4][4][4][2] = {
	{ //图案
		{ //旋转
			{ 0, 0 }, { -1, 0 }, { -2, 0 }, { 0, 1 } //坐标偏移
		},
		{
			{ 0, 0 }, { 0, 1 }, { 0, 2 }, { 1, 0 }
		},
		{
			{ 0, 0 }, { 0, -1 }, { 1, 0 }, { 2, 0 }
		},
		{
			{ 0, 0 }, { -1, 0}, { 0, -1 }, { 0, -2 }
		}
	},
	{
		{
			{ 0, 0 }, { 0, 1 }, { 0, 2 }, { 0, 3 }
		},
		{
			{ 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 }
		},
		{
			{ 0, 0 }, { 0, 1 }, { 0, 2 }, { 0, 3 }
		},
		{
			{ 0, 0 }, { 1, 0 }, { 2, 0 }, { 3, 0 }
		}
	},
	{
		{
			{ 0, 0 }, { 0, 1 }, { 0, -1 }, { 1, 0 }
		},
		{
			{ 0, 0 }, { 0, -1 }, { 1, 0 }, { -1, 0 }
		},
		{
			{ 0, 0 }, { -1, 0 }, { 0, -1 }, { 0, 1 }
		},
		{
			{ 0, 0 }, { 0, 1 }, { -1, 0 }, { 1, 0 }
		}
	},
	{
		{
			{ 0, 0 }, { 0, 1 }, { -1, 1 }, { -1, 2 }
		},
		{
			{ 0, 0 }, { 1, 0 }, { 1, 1 }, { 2, 1 }
		},
		{
			{ 0, 0 }, { 0, -1 }, { 1, -1 }, { 1, -2 }
		},
		{
			{ 0, 0 }, { -1, 0 }, { -1, -1 }, { -2, -1 }
		}
	}
};
void insert(int row, int col) {
	idle++;
	cnt[col]++;
	pos[idle] = { row, col };
	U[idle] = U[col];
	D[U[col]] = idle;
	U[col] = idle;
	D[idle] = col;
	if (!head[row]) head[row] = L[idle] = R[idle] = idle;
	else {
		L[idle] = L[head[row]];
		R[L[head[row]]] = idle;
		L[head[row]] = idle;
		R[idle] = head[row];
	}
}
int ind[N][N] = { 0 }; //为每个 '1' 分配列
void build() {
	memset(head, 0, sizeof head);
	memset(cnt, 0, sizeof cnt);
	memset(ind, 0, sizeof ind);
	m = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (arr[i][j] == '1')
				m++, ind[i][j] = m;
	m += 4; //为四个图形分配列
	for (int i = 0; i <= m; i++) {
		L[i] = i - 1, R[i] = i + 1;
		U[i] = D[i] = i;
		pos[i] = { 0, i };
	}
	idle = m;
	L[0] = m, R[m] = 0;
	int r = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			if (arr[i][j] == '1') {
				for (int t = 0; t < 4; t++) //遍历每个图案
					for (int d = 0; d < 4; d++) { //遍历每个角度
						bool f = true;
						for (int c = 0; c < 4; c++) { //查看每个偏移
							int dx = i + dir[t][d][c][0], dy = j + dir[t][d][c][1];
							if (dx < 1 || dy < 1 || dx > n || dy > n || arr[dx][dy] != '1') {
								f = false;
								break;
							}
						}
						if (f) {
							r++;
							insert(r, m - 3 + t);
							for (int c = 0; c < 4; c++) {
								int dx = i + dir[t][d][c][0], dy = j + dir[t][d][c][1];
								insert(r, ind[dx][dy]);
							}
						}
					}
				r++;
				insert(r, ind[i][j]);
			}
}
//冻结第 i 列及其关联行
void freeze(int col) {
	L[R[col]] = L[col], R[L[col]] = R[col];
	for (int i = D[col]; i != col; i = D[i])
		for (int j = R[i]; j != i; j = R[j])
			cnt[pos[j].y] --, U[D[j]] = U[j], D[U[j]] = D[j];
}
//激活第 i 列及其关联行
void active(int col) {
	L[R[col]] = R[L[col]] = col;
	for (int i = U[col]; i != col; i = U[i])
		for (int j = L[i]; j != i; j = L[j])
			cnt[pos[j].y] ++, U[D[j]] = j, D[U[j]] = j;
}
bool dance() {
	if (!R[0]) return true;
	int s = R[0];
	for (int i = R[s]; i; i = R[i])
		if (cnt[i] < cnt[s])
			s = i;
	freeze(s);
	for (int i = D[s]; i != s; i = D[i]) {
		for (int j = R[i]; j != i; j = R[j])
			freeze(pos[j].y);
		if (dance()) return true;
		for (int j = L[i]; j != i; j = L[j])
			active(pos[j].y);
	}
	active(s);
	return false;
}
int main() {
	int _;
	scanf("%d", &_);
	while (_--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				scanf(" %c", &arr[i][j]);
		build();
		if (dance()) puts("Yes");
		else puts("No");
	}
	return 0;
}