题解：P12533 [XJTUPC 2025] 9-Nine

· · 题解

题解：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 次。

  1. 处理棱块

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

  1. 处理角块

我们仿照样例，先通过至多 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; // 完结撒花
}