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

发表于 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 6 分钟

Problem

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

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

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

输入格式

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

初始魔方展开图

\(1\le T\le 10\)

Solution

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

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

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

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

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

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

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
/**************************************************************
 * 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;
}