首页 > 试题广场 >

附加题

[编程题]附加题
  • 热度指数:100 时间限制: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
TER头像 TER
无从下手
发表于 2020-03-31 17:42:07 回复(0)
利用dfs进行遍历,穷举所有的旋转结果
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    static int[][] Rotate = {
        // FRONT
        {0, 1, 11, 5, 4, 16, 12, 6, 2, 9, 10, 17, 13, 7, 3, 15, 14, 8, 18, 19, 20, 21, 22, 23},
        // BEHIND
        {9, 15, 2, 3, 1, 5, 6, 7, 8, 19, 0, 11, 12, 13, 14, 18, 16, 17, 4, 10, 22, 20, 23, 21},
        // LEFT
        {20, 1, 22, 3, 10, 4, 0, 7, 8, 9, 11, 5, 2, 13, 14, 15, 6, 17, 12, 19, 16, 21, 18, 23},
        // RIGHT
        {0, 7, 2, 13, 4, 5, 6, 17, 14, 8, 10, 11, 12, 19, 15, 9, 16, 21, 18, 23, 20, 1, 22, 3},
        // UP
        {2, 0, 3, 1, 6, 7, 8, 9, 23, 22, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 5, 4},
        // DOWN
        {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 21, 20, 10, 11, 12, 13, 18, 16, 19, 17, 15, 14, 22, 23}
    };
    
    static int[][] face = {
        {0, 1, 2, 3},
        {4, 5, 10, 11},
        {6, 7, 12, 13},
        {8, 9, 14, 15},
        {16, 17, 18, 19},
        {20,21, 22, 23}
    };
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] strMagic = br.readLine().trim().split(" ");
        int[] magic = new int[24];
        for(int i = 0; i < 24; i++) magic[i] = Integer.parseInt(strMagic[i]);
        System.out.println(dfs(magic, 5));
    }
    
    private static long dfs(int[] magic, int opNum) {
        // 计算此时的优美度
        long grace = getGrace(magic);
        // 已经没有操作机会,直接返回
        if(opNum == 0) return grace;
        // 分别旋转6个面一次
        for(int face_id = 0; face_id < 6; face_id++){
            // 注意不能直接在原始的魔方上旋转,因为需要回溯(撤销本次旋转,对另外一个面进行旋转)
            int[] temp = new int[24];
            for(int i = 0; i < 24; i++) temp[i] = magic[i];
            // 顺时针旋转1次,然后更新1次最大优美度
            rotate(temp, face_id);
            grace = Math.max(grace, dfs(temp, opNum - 1));
            // 逆时针旋转1次(相当于顺时针旋转3次),然后更新1次最大优美度
            rotate(temp, face_id);
            rotate(temp, face_id);
            grace = Math.max(grace, dfs(temp, opNum - 1));
        }
        return grace;
    }
    
    // 顺时针旋转操作,根据旋转矩阵调整索引位置即可
    private static void rotate(int[] magic, int face_id) {
        int[] temp = new int[24];
        for(int i = 0; i < 24; i++) temp[i] = magic[i];
        for(int i = 0; i < 24; i++) magic[i] = temp[Rotate[face_id][i]];
    }
    
    private static long getGrace(int[] magic) {
        long sum = 0, mul = 1;
        for(int i = 0; i < 6; i++){      // 遍历每个面
            mul = 1;
            // 计算每个面的优美度
            for(int j = 0; j < 4; j++)
                mul *= magic[face[i][j]];
            sum += mul;
        }
        return sum;
    }
}


发表于 2021-01-27 16:38:39 回复(0)
本题思路:BFS,模拟每次转动的经过,暴力破解,遍历次数12^5
(顺时针、逆时针)、(前、后、左、右、上、下)
发表于 2020-04-29 08:27:47 回复(0)
好难啊!
发表于 2019-11-04 20:18:23 回复(0)
bfs 模拟 
发表于 2019-09-28 13:04:58 回复(0)