自动搬运

查看原文

来自洛谷，原作者为

	zhylj 人生输家

搬运于2025-08-24 22:25:34，当前版本为作者最后更新于2021-11-07 16:56:12，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

不妨称三个矩阵分别为 $A,B,C$，问题等价于将三个矩阵平移后异或起来都为 $0$。

分别找到三个矩阵中最上面的 $1$ 中最左边的，我们断言：合法解中这三个 $1$ 必然有两个是重合的。证明考虑反证，若都不重合，考虑这三个点构成的图形中最上面的 $1$ 中最左边的，其必然不可能被其它另外的 $1$ 所覆盖，所以在最终的图形中必然为 $1$，显然不可能为解。

于是只有 $\mathcal O(1)$ 种可能，暴力 Check 即可，时间复杂度 $\mathcal O(n^2)$。

#define fi first
#define se second
#define mkp std::make_pair
#define NO mkp(INF, INF)
typedef std::pair <int, int> pii;
const int N = 4000 + 5, O = 2000, INF = 0x3f3f3f3f;

int h[3], w[3], mat[3][N][N], ans_mat[N][N]; pii top_l[3];
char s[N];

void GetAnsMat(int t_1, int t_2, int mov_x, int mov_y) {
	memset(ans_mat, 0, sizeof(ans_mat)); 
	for(int i = 1; i <= h[t_1]; ++i)
		for(int j = 1; j <= w[t_1]; ++j)
			ans_mat[O + i][O + j] ^= mat[t_1][i][j];
	for(int i = 1; i <= h[t_2]; ++i)
		for(int j = 1; j <= w[t_2]; ++j)
			ans_mat[O + i + mov_x][O + j + mov_y] ^= mat[t_2][i][j];
}

std::vector <pii> a, b;
pii Check(int t) {
	a.clear(); b.clear();
	for(int i = 0; i < N; ++i)
		for(int j = 0; j < N; ++j) {
			if(mat[t][i][j]) a.push_back(mkp(i, j));
			if(ans_mat[i][j]) b.push_back(mkp(i - O, j - O));
		}
	if(a.size() != b.size()) return NO;
	if(a.size() == 0) return mkp(0, 0);
	int mov_x = b[0].fi - a[0].fi, mov_y = b[0].se - a[0].se;
	for(int i = 0; i < a.size(); ++i)
		if(b[i].fi != mov_x + a[i].fi || b[i].se != mov_y + a[i].se) return NO;
	return mkp(mov_x, mov_y);
}

int main() {
	for(int t = 0; t < 3; ++t) {
		scanf("%d%d", &h[t], &w[t]);
		top_l[t] = mkp(0, 0);
		for(int i = 1; i <= h[t]; ++i) {
			scanf("%s", s + 1);
			for(int j = 1; j <= w[t]; ++j) {
				mat[t][i][j] = (s[j] == '*');
				if(top_l[t] == mkp(0, 0) && s[j] == '*')
					top_l[t] = mkp(i, j);
			}
		}
	}
	int mov_x, mov_y; pii tmp;
	mov_x = top_l[0].fi - top_l[1].fi;
	mov_y = top_l[0].se - top_l[1].se;
	GetAnsMat(0, 1, mov_x, mov_y);
	tmp = Check(2);
	if(tmp != NO) {
		printf("YES\n%d %d\n", mov_y, mov_x);
		continue;
	}
	mov_x = top_l[0].fi - top_l[2].fi;
	mov_y = top_l[0].se - top_l[2].se;
	GetAnsMat(0, 2, mov_x, mov_y);
	tmp = Check(1);
	if(tmp != NO) {
		printf("YES\n%d %d\n", tmp.se, tmp.fi);
		continue;
	}
	mov_x = top_l[1].fi - top_l[2].fi;
	mov_y = top_l[1].se - top_l[2].se;
	GetAnsMat(1, 2, mov_x, mov_y);
	tmp = Check(0);
	if(tmp != NO) {
		printf("YES\n%d %d\n", -tmp.se, -tmp.fi);
		continue;
	}
	printf("NO\n");
	return 0;
}