牛客网 字节跳动算法题-二阶魔方最大优美度

描述

二阶魔方又叫小魔方，是222的立方形结构。每一面都有4个块，共有24个块。每次操作可以将任意一面逆时针或者顺时针旋转90°，如将上面逆时针旋转90°操作如下。

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

输入描述：

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

输出描述：

输出一行包含一个数字，表示最大优美度。

题解：

魔方的旋转会使得数组的值进行交换。每次旋转变动的是一周8个数字，和旋转面4个数字。
此为二阶魔方，只需考虑3个面的旋转情况；
旋转有顺时针旋转和逆时针旋转，不过顺时针（逆时针）旋 转可以通过旋转3次逆时针（顺时针）得到。
因此根据旋转规律声明turn旋转数组
考察DFS算法，深搜每种旋转情况，旋转完成计算一次当前最大优美度。

import java.util.*;
public class Main{public static int [][] turn = {//三面逆时针旋转，数组中每四个为一组{0,1,3,2,7,5,22,9,6,4,23,8},{6,7,13,12,2,8,17,11,3,14,16,5},{4,5,11,10,0,6,16,20,2,12,18,22},};public static int max = Integer.MIN_VALUE;public static void main(String []args){Scanner scanner = new Scanner(System.in);int[] n = new int[24];for(int i = 0; i < 24; i++) {n[i] = scanner.nextInt();}dfs(n, 0);System.out.println(max);}public static void dfs(int[] n, int depth) {// 非法状态if (depth == 6) return ;// 当前状态优美度int res = compute(n);max = Math.max(res,max);//逆时针旋转for (int i = 0; i < 3; i++) {swap(n,i);//旋转完成进入下一层dfs(n,depth+1);swap(n,i);swap(n,i);swap(n,i);}//顺时针旋转for (int j = 0; j < 3; j++) {swap(n,j);swap(n,j);swap(n,j);//旋转完成进入下一层dfs(n,depth+1);swap(n,j);}}//每次旋转后交换数组的值public static void swap (int[] n,int type) {// 每四个下标一轮回for (int i = 0, tmp = 0; i < 12; i++) {if (i % 4 == 0) tmp = n[turn[type][i]];if (i % 4 == 3) n[turn[type][i]] = tmp;else n[turn[type][i]] = n[turn[type][i+1]];}}//计算优美度public static int compute (int[] n) {return n[0]*n[1]*n[2]*n[3] +n[6]*n[7]*n[12]*n[13] +n[4]*n[5]*n[10]*n[11] +n[8]*n[9]*n[14]*n[15] +n[16]*n[17]*n[18]*n[19] +n[20]*n[21]*n[22]*n[23];}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！