首页 > 试题广场 >

附加题

[编程题]附加题
  • 热度指数:225 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
二阶魔方又叫小魔方,是2*2*2的立方形结构。每一面都有4个块,共有24个块。每次操作可以将任意一面逆时针或者顺时针旋转90°,如将上面逆时针旋转90°操作如下。

Nero在小魔方上做了一些改动,用数字替换每个块上面的颜色,称之为数字魔方。魔方上每一面的优美度就是这个面上4个数字的乘积,而魔方的总优美度就是6个面优美度总和。
现在Nero有一个数字魔方,他想知道这个魔方在操作不超过5次的前提下能达到的最大优美度是多少。
魔方展开后每一块的序号如下图:

输入描述:
输入一行包含24个数字,按序号顺序给出魔方每一块上面的数字。所有数大小范围为[-100,100]。


输出描述:
输出一行包含一个数字,表示最大优美度。
示例1

输入

2 -3 -2 3 7 -6 -6 -7 9 -5 -9 -3 -2 1 4 -9 -1 -10 -5 -5 -10 -4 8 2

输出

8281
发表于 2018-03-07 09:10:51 回复(0)
魔方的旋转方式大致可分为三个(顺时针可以通过对应逆时针旋转三次实现),右面(Y)逆时针,后面(X)逆时针,上面(Z)逆时针,封装成三个函数,分析发现,所有的旋转可以归结为一圈八个块的位置轮转(函数zheng)和一个侧面四个小块的位置轮换(函数ce)。
不超过5次的操作,可以通过一个类似深度优先遍历操作实现(这里会有很多重复,暂时没有优化)
#include<iostream>
#include<vector>
using namespace std;

#define DEPTH 5

class moFang{
    private:
    vector<int> list;
    vector<vector<int>> pos = {
        {0,1,2,3},        //up 0
        {4,5,10,11},        //left 1
        {6,7,12,13},        //before 2
        {8,9,14,15},        //right 3
        {16,17,18,19},        //down 4
        {20,21,22,23}        //behind 5
    };
    
    void zheng(int p1, int p2, int p3, int p4, int p5, int p6, int p7, int p8){
        int temp1 = list[p7], temp2 = list[p8];
        list[p7] = list[p5]; list[p8] = list[p6];
        list[p5] = list[p3]; list[p6] = list[p4];
        list[p3] = list[p1]; list[p4] = list[p2];
        list[p1] = temp1; list[p2] = temp2;
    }
    
    void ce(int p1, int p2, int p3, int p4){
        int temp = list[p4];
        list[p4] = list[p3];
        list[p3] = list[p2];
        list[p2] = list[p1];
        list[p1] = temp;
    }
    
    
    public:
    
    void add(int n){ list.push_back(n); }
    
    void turnY(){
        zheng(pos[0][1], pos[0][3], pos[2][1], pos[2][3], pos[4][1], pos[4][3], pos[5][1], pos[5][3]);
        ce(pos[3][0], pos[3][2], pos[3][3], pos[3][1]);
    }
    void turnX(){
        zheng(pos[0][0], pos[0][1], pos[3][1], pos[3][3], pos[4][3], pos[4][2], pos[1][2], pos[1][0]);
        ce(pos[5][3], pos[5][1], pos[5][0], pos[5][2]);
    }
    void turnZ(){
        zheng(pos[1][0], pos[1][1], pos[2][0], pos[2][1], pos[3][0], pos[3][1], pos[5][3], pos[5][2]);
        ce(pos[0][2], pos[0][3], pos[0][1], pos[0][0]);
    }
    
    int getSum(){
        int sum = 0, tempsum = 1;
        for(int i=0;i<6;i++){
            for(int j=0;j<4;j++){
                tempsum *= list[pos[i][j]];
            }
            sum += tempsum;
            tempsum = 1;
        }
        return sum;
    }
    
    
    int getMax(int dep){
        int max = getSum(), temp=0;
        turnY();
        temp = getSum();
        if(temp>max) max=temp;
        if(dep<DEPTH) {
            temp = getMax(dep+1);
            if(temp>max) max=temp;
        }
        turnY();
        turnY();
        temp = getSum();
        if(temp>max) max=temp;
        if(dep<DEPTH) {
            temp = getMax(dep+1);
            if(temp>max) max=temp;
        }
        turnY();
        turnX();
        temp = getSum();
        if(temp>max) max=temp;
        if(dep<DEPTH) {
            temp = getMax(dep+1);
            if(temp>max) max=temp;
        }
        turnX();
        turnX();
        temp = getSum();
        if(temp>max) max=temp;
        if(dep<DEPTH) {
            temp = getMax(dep+1);
            if(temp>max) max=temp;
        }
        turnX();
        turnZ();
        temp = getSum();
        if(temp>max) max=temp;
        if(dep<DEPTH) {
            temp = getMax(dep+1);
            if(temp>max) max=temp;
        }
        turnZ();
        turnZ();
        temp = getSum();
        if(temp>max) max=temp;
        if(dep<DEPTH) {
            temp = getMax(dep+1);
            if(temp>max) max=temp;
        }
        turnZ();
        
        return max;
    }
};

int main(){
    moFang m;
    int n;
    for(int i=0;i<24;i++){
        cin>>n;
        m.add(n);
    }
    
    cout << m.getMax(1) << endl;
    
    return 0;
}


编辑于 2019-08-17 23:25:56 回复(0)