自动搬运

查看原文

来自洛谷，原作者为

	_hud Hi

搬运于2025-08-24 23:16:16，当前版本为作者最后更新于2025-05-20 06:49:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题解：P12533 [XJTUPC 2025] 9-Nine

题目大意

给定两个 $3 \times 3$ 的 01 矩阵 $A$ 和 $B$，需通过以下操作在 $81$ 步内将 $A$ 变为全 0 矩阵，同时 $B$ 变为全 1 矩阵：

1. 旋转操作：对 $A$ 或 $B$ 左旋（逆时针）或右旋（顺时针）$90^\circ$；
2. 交换操作：选择一列 $k$，交换 $A$ 和 $B$ 的第 $k$ 列。

思路分析

一道很好的构造题。

为了方便讲解，我们引入魔方中的概念：称矩阵 $A$ 中心元素为中心块，矩阵 $A$ 四个角上的元素为角块，其余元素为棱块。

观察样例不难发现，所给样例即是在不影响其他位置元素的前提下，交换 $A$ 和 $B$ 中两个角块的操作步骤。故我们往这个方向思考，棱块、中心块也一定能通过类似方法复原到正确的位置上。我们逐一分析：

1. 处理中心块

显然，若 $A$ 的中心块为 1，直接交换中间列（操作 C2），使得中心为 0 即可。本步至多操作 $1$ 次。

2. 处理棱块

我们可以先通过至多 $2 \times 2 = 4$ 次旋转操作将 $A$ 中为 $1$ 的棱块和 $B$ 中为 $0$ 的棱块置于第二行第一列，然后交换第一列（操作 C1）即可。本步至多操作 $(4 + 1) \times 4 = 20$ 次。

3. 处理角块

我们仿照样例，先通过至多 $2 \times 2 = 4$ 次旋转操作将 $A$ 中为 1 的角块置于第三行第一列，将 $B$ 中为 0 的角块置于第一行第一列，然后通过样例中给出的操作（即 C1，AL，C1，AR，C1）交换两个角块即可。本步至多操作 $(4 + 5) \times 4 = 36$ 次。

统计以上三步的步数，至多需要 $1 + 20 + 36 = 57$ 次，远小于题目要求的 $81$ 次。可以通过此题。

同时，还需要通过模拟实现旋转和交换列的操作，这里就不细讲了。具体可以看代码。

代码

#include <bits/stdc++.h>
using namespace std;
#define DEBUG { cout << '\n' << a[1] << ' ' << a[2] << ' ' << a[3] << '\n' << b[1] << ' ' << b[2] << ' ' << b[3] << "\n\n"; }
string a[4], b[4], opts[82];
int opt;
inline void C(int x) {
    opts[opt++] = "C" + to_string(x);
	char t0 = a[1][x], t1 = a[2][x], t2 = a[3][x];
    a[1][x] = b[1][x], a[2][x] = b[2][x], a[3][x] = b[3][x], b[1][x] = t0, b[2][x] = t1, b[3][x] = t2;
}
inline void AL() {
    opts[opt++] = "AL";
	string t1 = a[1], t2 = a[2], t3 = a[3];
	a[1][1] = t1[3], a[1][2] = t2[3], a[1][3] = t3[3], a[2][1] = t1[2], a[2][2] = t2[2], a[2][3] = t3[2], a[3][1] = t1[1], a[3][2] = t2[1], a[3][3] = t3[1];
}
inline void AR() {
    opts[opt++] = "AR";
	string t1 = a[1], t2 = a[2], t3 = a[3];
	a[1][1] = t3[1], a[1][2] = t2[1], a[1][3] = t1[1], a[2][1] = t3[2], a[2][2] = t2[2], a[2][3] = t1[2], a[3][1] = t3[3], a[3][2] = t2[3], a[3][3] = t1[3];
}
inline void BL() {
    opts[opt++] = "BL";
	string t1 = b[1], t2 = b[2], t3 = b[3];
	b[1][1] = t1[3], b[1][2] = t2[3], b[1][3] = t3[3], b[2][1] = t1[2], b[2][2] = t2[2], b[2][3] = t3[2], b[3][1] = t1[1], b[3][2] = t2[1], b[3][3] = t3[1];
}
inline void BR() {
    opts[opt++] = "BR";
	string t1 = b[1], t2 = b[2], t3 = b[3];
	b[1][1] = t3[1], b[1][2] = t2[1], b[1][3] = t1[1], b[2][1] = t3[2], b[2][2] = t2[2], b[2][3] = t1[2], b[3][1] = t3[3], b[3][2] = t2[3], b[3][3] = t1[3];
}
signed main() {
    cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
    for(int i = 1; i <= 3; i++) cin >> a[i], a[i] = " " + a[i];
    for(int i = 1; i <= 3; i++) cin >> b[i], b[i] = " " + b[i];
    // 第一步：处理中心块
    if(a[2][2] == '1') C(2);
    // 第二步：处理棱块
    for(int i = 0; i < 4; i++) {
		if(a[1][2] == '1') AL();
		else if(a[2][3] == '1') AR(), AR();
		else if(a[3][2] == '1') AR();
		if(a[2][1] == '1') {
			if(b[2][1] == '0') {}
			else if(b[1][2] == '0') BL();
			else if(b[2][3] == '0') BR(), BR();
			else BR();
			C(1);
        }
	}
    // 第三步：处理角块
    for(int i = 0; i < 4; i++) {
		if(a[1][3] == '1') AL(), AL();
		else if(a[1][1] == '1') AL();
		else if(a[3][3] == '1') AR();
		if(a[3][1] == '1') {
			if(b[1][1] == '0') {}
			else if(b[1][3] == '0') BL();
			else if(b[3][1] == '0') BR();
			else BR(), BR();
			C(1), AL(), C(1), AR(), C(1);
		}
	}
    cout << opt << '\n';
    for(int i = 0; i < opt; i++) cout << opts[i] << '\n';
    return 0; // 完结撒花
}