题解：P12533 [XJTUPC 2025] 9-Nine

jqQt0220 · 2025-10-03 16:49:56 · 题解

模拟赛的题，场切了（）

爆搜+剪枝即可。每个矩阵使用一个 vector<vector<char> > 存储，操作用 vector<string> 存，每次往下搜前加入操作，搜完把尾删掉回溯。最后判断 A 矩阵是否全 0 且操作数 \le81 就行了。

但是显然，直接爆搜是 O(7^{81}) 的，会 T 飞。所以要剪枝：

• 可行性剪枝：操作数 >81 了就不用往下搜了，因为搜完也达不到要求；
• 最优性剪枝：利用 map 存下到达两个矩阵的某种状态的最小操作数，多了就不用搜了。

代码：

#define ll long long
const int _mxn=+5;
typedef vector<vector<char> > vvc;
typedef pair<vvc,vvc> pvv;
vvc a,b;
vector<string> op;
bool check(vvc a)//判断是否完成
{
    for(int i=1;i<=3;i++)
        for(int j=1;j<=3;j++)
            if(a[i][j]=='1')
                return false;
    return true;
}
void change(vvc &a,vvc &b,int k)//交换列
{
    for(int i=1;i<=3;i++)
        swap(a[i][k],b[i][k]);
}
void turn(vvc &a,int d)//旋转，d=0 L，d=1 R
{
    vvc tmp;tmp=a;
    if(d==0)
    {
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
                a[i][j]=tmp[j][4-i];
    }
    else
    {
        for(int i=1;i<=3;i++)
            for(int j=1;j<=3;j++)
                a[i][j]=tmp[4-j][i];
    }
}
map<vvc,map<vvc,int> > f;//到该状态的最少操作数
string st[]={"C1","C2","C3","AL","AR","BL","BR"};
void dfs(vvc a,vvc b)
{
    if(op.size()>81)//可行性剪枝
        return;

    if(f[a][b]<=op.size())//最优性剪枝
        return;
    f[a][b]=op.size();

    // for(int i=1;i<=3;i++,cout<<endl)
    //     for(int j=1;j<=3;j++)
    //         cout<<a[i][j];
    // for(int i=1;i<=3;i++,cout<<endl)
    //     for(int j=1;j<=3;j++)
    //         cout<<b[i][j];
    // cout<<endl;

    if(check(a))
    {
        cout<<op.size()<<endl;
        for(string s:op)
            cout<<s<<endl;
        exit(0);
    }

    vvc ta,tb;
    for(int i=1;i<=7;i++)
    {
        ta=a,tb=b;
        if(i<=3)
            change(ta,tb,i);
        else
        {
            if((i-4)/2==0)
                turn(ta,i%2);
            else
                turn(tb,i%2);
        }
        op.push_back(st[i-1]);
        dfs(ta,tb);
        op.pop_back();//回溯
    }
}
int main()
{
    ___();
    a.resize(4);
    for(int i=1;i<=3;i++)
    {
        a[i].resize(4);
        for(int j=1;j<=3;j++)
            cin>>a[i][j];
    }
    b.resize(4);
    for(int i=1;i<=3;i++)
    {
        b[i].resize(4);
        for(int j=1;j<=3;j++)
            cin>>b[i][j];
    }
    vvc ta,tb;
    ta=a,tb=b;
    for(int i=(1<<9)-1;i<(1<<18);i++)//枚举所有可能的状态并初始化 f
    {
        if(__builtin_popcount(i)==9)//总共一定有 9 个 1
        {
            for(int j=0;j<18;j++)
            {
                int t=(i>>j)&1;
                if(j<9)
                    ta[j/3+1][j%3+1]=t+'0';
                else
                    tb[(j-9)/3+1][j%3+1]=t+'0';
            }
            f[ta][tb]=1e9;
        }
    }
    dfs(a,b);
    return 0;
}