HDU6202 Cube Cube Cube

98 阅读 0 评论 65 点赞

我是靠谱客的博主欢喜乐曲，最近开发中收集的这篇文章主要介绍HDU6202 Cube Cube Cube，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

模拟题。

大概就是问你一个魔方三步之内能不能还原。
是个金字塔魔方。

比赛的时候写了个300行的wa了，以为是旋转写错了，检查了半天，结果后来发现是dfs写傻逼了。好难过啊。

后来想了想写了个100行的。

这个魔方有24个操作。分别是8个面顺逆，四个中间顺逆。
发现逆时针就是顺时针转两下。还有中间顺就是一个边上的面顺转一次，另外一个逆转一次。然后对于每个面，四周的序列也很有规律。仔细一点就可以过了。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
    int a[73];
    int d[3][4] = {{2,-1,4,-1},{1,1,1,1},{-1,-4,-1,-2}};
    bool check(){
        for(int i = 1;i <= 8;i++){
            for(int j = 2;j <= 9;j++){
                if(a[(i - 1) * 9 + 1] != a[(i - 1) * 9 + j]) return false;
            }
        }
        return true;
    }
    void R(int i,int j,int k){
        int tmp = a[k];a[k] = a[j];a[j] = a[i];a[i] = tmp;
    }
    void rotate(int n){//面顺时针旋转
        R(n,n + 8,n + 4);
        R(n + 3,n + 6,n + 1);
        R(n + 2,n + 7,n + 5);
    }
    void change(int c[][6]){
        for(int i = 0;i < 6;i++){
            R(c[0][i],c[1][i],c[2][i]);
        }
    }
    int e[8][6] = {{10,41,36,54,68,19},{19,50,9,63,41,28},{28,59,18,72,50,1},{1,68,27,45,59,10},{64,5,54,36,14,55}
            ,{37,14,63,9,23,64},{46,23,72,18,32,37},{55,32,45,27,5,46}};
    void OP(int t){
        if(t <= 16){
            if(t & 1){
                int x = t / 2;
                rotate(x * 9 + 1);
                int b[3][6];
                for(int i = 0;i < 3;i++){
                    b[i][0] = e[x][i];
                }
                for(int i = 0;i < 3;i++){
                    b[i][5] = e[x][i + 3];
                }
                for(int i = 0;i < 4;i++){
                    for(int j = 0;j < 3;j++){
                        b[j][i + 1] = b[j][i] + d[j][i];
                    }
                }
                change(b);
            }else{
                OP(t - 1);OP(t - 1);
            }
        }
        else{
            if(t & 1){
                if(t == 17){
                    OP(5);OP(9);OP(9);
                }
                if(t == 19){
                    OP(7);OP(11);OP(11);
                }
                if(t == 21){
                    OP(13);OP(1);OP(1);
                }
                if(t == 23){
                    OP(3);OP(15);OP(15);
                }
            }
            else{
                OP(t - 1);OP(t - 1);
            }
        }
    }
    void read(){
        for(int i = 1;i <= 72;i++){
            scanf("%d",&a[i]);
        }
    }
    bool dfs(int dep){
        if(check()) return true;
        if(dep >= 4) return false;

        for(int i = 1;i <= 24;i++){
            OP(i);
            if(dfs(dep + 1)) return true;
            if(i & 1) OP(i + 1);
            else OP(i - 1);
        }
        return false;
    }

int main(){
    int T;
    cin >> T;
    while(T--){
        read();
        if(dfs(1)) cout << "YES" << endl;
        else cout << "NO" << endl;
    }
    return 0;
}

/*
 2
 6 1 1 1 3 1 1 1 1
2 4 2 2 4 4 7 7 7
8 3 3 3 8 3 3 3 1
5 4 5 5 5 5 5 2 2
7 2 7 7 2 2 2 7 7
3 6 6 6 6 6 6 6 3
4 4 4 5 4 4 7 5 5
8 8 8 8 6 8 8 8 1

 1 1 1 1 1 1 1 1 3
2 2 2 2 7 7 7 7 7
3 3 3 3 8 3 3 3 3
4 4 4 4 4 4 4 4 4
2 2 2 5 2 2 5 5 5
6 6 6 6 6 6 6 6 6
5 7 5 5 7 7 7 5 5
1 8 8 8 8 8 8 8 8

 1
 1 1 1 1 1 1 1 1 1
 4 4 4 2 4 4 2 2 2
 8 3 3 3 3 3 3 3 3
 5 4 5 5 4 4 4 5 5
 5 5 5 5 2 2 2 2 2
 6 6 6 6 6 6 6 6 3
 7 7 7 7 7 7 7 7 7
 8 8 8 8 6 8 8 8 8
 */





/*
1
1 1 1 1 1 1 1 1 1
4 4 4 2 4 4 2 2 2
8 3 3 3 3 3 3 3 3
5 4 5 5 4 4 4 5 5
5 5 5 5 2 2 2 2 2
6 6 6 6 6 6 6 6 3
7 7 7 7 7 7 7 7 7
8 8 8 8 6 8 8 8 8
 */