2024杭电钉耙2-1003 HDOJ7447 绝对不模拟的简单魔方

Problem

有一个魔方可能被拧了不超过三次，同时还弄丢了一个角块上的两个贴纸。现在把这两个贴纸贴回去，请问有没有贴错？

只可能拧侧面，不会拧中间层，且每次只能拧 $90^\circ$。

魔方用一个 9 行 12 列的字符型矩阵表示：

初始魔方的展开图如下图：

$1\le T\le 10$

Solution

说实话没啥好考虑的，可能有取巧的方法？但是我不太想思考。

定义一个魔方类 Cube，包含了一个二维字符数组。只需要写六个成员函数（对应六种旋转操作），就可以描述这个魔方的所有旋转情况。

然后进行 dfs 搜索每一种可能的情况，并且与初始魔方展开图进行比较。

如果当前状态与展开图对比，不同的字符不超过两个，则说明复原成功。

• 如果完全相同，则没有贴错，输出 No problem。
• 如果有两个不相同，则贴错了，输出错误角块对应的三个数字。

没啥好多说的。Talk is cheap.Show me the code.

Code

/**************************************************************
 * Problem: 
 * Author: Vanilla_chan
 * Date: 
 * E-Mail: heshaohong2015@outlook.com
 **************************************************************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<limits.h>
#define IL inline
#define re register
#define LL long long
#define ULL unsigned long long
#ifdef TH
#define debug printf("Now is %d\n",__LINE__);
#else
#define debug
#endif
#ifdef ONLINE_JUDGE
char buf[1<<23],* p1=buf,* p2=buf,obuf[1<<23],* O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
#endif
using namespace std;

#define pii pair<int,int>
#define mk(a,b) make_pair(a,b)
/*
***111******
***111******
***111******
222333444555
222333444555
222333444555
***666******
***666******
***666******
*/

#define N 1000
struct Cube
{
    string str[20];
    Cube()
    {
        for(int i=0;i<20;i++) str[i]="!!!!!!!!!!!!!!!!";
        str[0]="***111******";
        str[1]="***111******";
        str[2]="***111******";
        str[3]="222333444555";
        str[4]="222333444555";
        str[5]="222333444555";
        str[6]="***666******";
        str[7]="***666******";
        str[8]="***666******";
        
    }
    void output()
    {
        for(int i=0;i<9;i++) cout<<str[i]<<endl;
        cout<<endl;
    }
    void top()
    {
//        debug
        str[3]=str[3].substr(3,9)+str[3].substr(0,3);
        string ss[20];
        int mp[9][4]={1,4,1,5,1,5,1,6,1,6,2,6,2,6,3,6,3,6,3,5,3,5,3,4,3,4,2,4,2,4,1,4};
        for(int i=0;i<9;i++) for(int j=0;j<4;j++) mp[i][j]--;
        for(int t=0;t<2;t++)
        {
//            debug
            for(int i=0;i<9;i++) ss[i]=str[i];
            for(int k=0;k<8;k++)
            {
//                debug
                str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
            }
        }
    }
    void down()
    {
        str[5]=str[5].substr(3,9)+str[5].substr(0,3);
        string ss[20];
        int mp[9][4]={7,4,7,5,7,5,7,6,7,6,8,6,8,6,9,6,9,6,9,5,9,5,9,4,9,4,8,4,8,4,7,4};
        for(int i=0;i<9;i++) for(int j=0;j<4;j++) mp[i][j]--;
        for(int t=0;t<2;t++)
        {
            for(int i=0;i<9;i++) ss[i]=str[i];
            for(int k=0;k<8;k++)
            {
                str[mp[k][0]][mp[k][1]]=ss[mp[k][2]][mp[k][3]];
            }
        }
    }
    void right()
    {
        string ss[20];
        int mp[9][4]={4,7,4,8,4,8,4,9,4,9,5,9,5,9,6,9,6,9,6,8,6,8,6,7,6,7,5,7,5,7,4,7};
        for(int i=0;i<9;i++) for(int j=0;j<4;j++) mp[i][j]--;
        for(int i=0;i<9;i++) ss[i]=str[i];
        for(int t=0;t<2;t++)
        {
            for(int i=0;i<9;i++) ss[i]=str[i];
            for(int k=0;k<8;k++)
            {
                str[mp[k][0]][mp[k][1]]=ss[mp[k][2]][mp[k][3]];
            }
        }
        
        for(int i=11;i>=3;i--) str[i][5]=str[i-3][5];
        
        int mp1[9][4]={4,10,3,6,5,10,2,6,6,10,1,6};
        memcpy(mp,mp1,sizeof(mp));
        for(int i=0;i<3;i++) for(int j=0;j<4;j++) mp[i][j]--;
        for(int i=0;i<20;i++) ss[i]=str[i];
        for(int k=0;k<3;k++)
        {
            str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
        }
        
        int mp2[9][4]={10,6,6,10,11,6,5,10,12,6,4,10};
        memcpy(mp,mp2,sizeof(mp));
        for(int i=0;i<3;i++) for(int j=0;j<4;j++) mp[i][j]--;
        for(int i=0;i<20;i++) ss[i]=str[i];
        for(int k=0;k<3;k++)
        {
            str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
        }
    }
    void left()
    {
        string ss[20];
        int mp[9][4]={4,1,5,1,5,1,6,1,6,1,6,2,6,2,6,3,6,3,5,3,5,3,4,3,4,3,4,2,4,2,4,1};
        for(int i=0;i<9;i++) for(int j=0;j<4;j++) mp[i][j]--;
        for(int i=0;i<9;i++) ss[i]=str[i];
        for(int t=0;t<2;t++)
        {
            for(int i=0;i<9;i++) ss[i]=str[i];
            for(int k=0;k<8;k++)
            {
                str[mp[k][0]][mp[k][1]]=ss[mp[k][2]][mp[k][3]];
            }
        }
        for(int i=11;i>=3;i--) str[i][3]=str[i-3][3];
        
        int mp1[9][4]={4,12,3,4,5,12,2,4,6,12,1,4};
        memcpy(mp,mp1,sizeof(mp));
        for(int i=0;i<3;i++) for(int j=0;j<4;j++) mp[i][j]--;
        for(int i=0;i<20;i++) ss[i]=str[i];
        for(int k=0;k<3;k++)
        {
            str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
        }
        
        int mp2[9][4]={10,4,6,12,11,4,5,12,12,4,4,12};
        memcpy(mp,mp2,sizeof(mp));
        for(int i=0;i<3;i++) for(int j=0;j<4;j++) mp[i][j]--;
        for(int i=0;i<20;i++) ss[i]=str[i];
        for(int k=0;k<3;k++)
        {
            str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
        }
    }
    
    void front()
    {
        string ss[20];
        int mp[20][4]={4,4,5,4,5,4,6,4,6,4,6,5,6,5,6,6,6,6,5,6,5,6,4,6,4,6,4,5,4,5,4,4};
        for(int i=0;i<8;i++) for(int j=0;j<4;j++) mp[i][j]--;
        for(int i=0;i<9;i++) ss[i]=str[i];
        for(int t=0;t<2;t++)
        {
            for(int i=0;i<9;i++) ss[i]=str[i];
            for(int k=0;k<8;k++)
            {
                str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
            }
        }
        int mp1[30][4]={4,7,3,4,3,4,6,3,6,3,7,6,7,6,4,7,5,7,3,5,3,5,5,3,5,3,7,5,7,5,5,7,6,7,3,6,3,6,4,3,4,3,7,4,7,4,6,7};
        memcpy(mp,mp1,sizeof(mp));
        for(int i=0;i<12;i++) for(int j=0;j<4;j++) mp[i][j]--;
        for(int i=0;i<9;i++) ss[i]=str[i];
        for(int t=0;t<1;t++)
        {
            for(int i=0;i<9;i++) ss[i]=str[i];
            for(int k=0;k<12;k++)
            {
                str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
            }
        }
    }
    
    void back()
    {
        string ss[20];
        int mp[20][4]={4,10,5,10,5,10,6,10,6,10,6,11,6,11,6,12,6,12,5,12,5,12,4,12,4,12,4,11,4,11,4,10};
        for(int i=0;i<8;i++) for(int j=0;j<4;j++) mp[i][j]--;
        for(int i=0;i<9;i++) ss[i]=str[i];
        for(int t=0;t<2;t++)
        {
            for(int i=0;i<9;i++) ss[i]=str[i];
            for(int k=0;k<8;k++)
            {
                str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
            }
        }
        int mp1[20][4]={4,9,1,4,1,4,6,1,6,1,9,6,9,6,4,9,5,9,1,5,1,5,5,1,5,1,9,5,9,5,5,9,6,9,1,6,1,6,4,1,4,1,9,4,9,4,6,9};
        memcpy(mp,mp1,sizeof(mp));
        for(int i=0;i<12;i++) for(int j=0;j<4;j++) mp[i][j]--;
        for(int i=0;i<9;i++) ss[i]=str[i];
        for(int t=0;t<1;t++)
        {
            for(int i=0;i<9;i++) ss[i]=str[i];
            for(int k=0;k<12;k++)
            {
                str[mp[k][2]][mp[k][3]]=ss[mp[k][0]][mp[k][1]];
            }
        }
    }
    
};

bool found=0;


map<pii,string>out;


void check(Cube cube)
{
    Cube ans;
    int diff=0;
    pii pos;
    for(int i=0;i<9;i++)
    {
        for(int j=0;j<12;j++)
        {
            if(cube.str[i][j]!=ans.str[i][j])
            {
                diff++;
                pos=make_pair(i,j);
            }
        }
    }
    pos.first++;
    pos.second++;
    if(diff==0||diff==2)
    {
        found=1;
        if(diff)
        {
            cout<<out[pos]<<endl;
        }
        else
        {
            cout<<"No problem"<<endl;
        }
    }
}
void dfs(int depth,Cube cube)
{
    if(found) return;
    check(cube);
    if(found) return;
    if(depth>=3) return;
    Cube nxt;
    
    for(int i=0;i<=1;i++)
    {
        int t=i?1:3;
        nxt=cube;
        while(t--) nxt.front();
        dfs(depth+1,nxt);
        
        t=i?1:3;
        nxt=cube;
        while(t--) nxt.back();
        dfs(depth+1,nxt);
        
        t=i?1:3;
        nxt=cube;
        while(t--) nxt.left();
        dfs(depth+1,nxt);
        
        t=i?1:3;
        nxt=cube;
        while(t--) nxt.right();
        dfs(depth+1,nxt);
        
        t=i?1:3;
        nxt=cube;
        while(t--) nxt.top();
        dfs(depth+1,nxt);
        
        t=i?1:3;
        nxt=cube;
        while(t--) nxt.down();
        dfs(depth+1,nxt);
    }
    
    
}

int main()
{
    out[mk(4,3)]=out[mk(4,4)]=out[mk(3,4)]="1 2 3";
    out[mk(1,4)]=out[mk(4,1)]=out[mk(4,12)]="1 2 5";
    out[mk(1,6)]=out[mk(4,9)]=out[mk(4,10)]="1 4 5";
    out[mk(3,6)]=out[mk(4,6)]=out[mk(4,7)]="1 3 4";
    out[mk(6,1)]=out[mk(9,4)]=out[mk(6,12)]="2 5 6";
    out[mk(6,3)]=out[mk(6,4)]=out[mk(7,4)]="2 3 6";
    out[mk(6,6)]=out[mk(6,7)]=out[mk(7,6)]="3 4 6";
    out[mk(9,6)]=out[mk(6,9)]=out[mk(6,10)]="4 5 6";
    
    
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cout.precision(10);
    
//    Cube test;
//    test.str[0]="***123******";
//    while(1)
//    {
//        string cmd;cin>>cmd;
//        if(cmd=="left") test.left();
//        if(cmd=="right") test.right();
//        if(cmd=="down") test.down();
//        if(cmd=="top") test.top();
//        if(cmd=="back") test.back();
//        if(cmd=="front") test.front();
//        test.output();
//    }
    
    
    int t=1;
    cin>>t;
    while(t--)
    {
        found=0;
        Cube cube;
        for(int i=0;i<9;i++) cin>>cube.str[i];
        dfs(0,cube);
        
    }
    return 0;
}