附加题

[编程题]附加题

热度指数：1879 时间限制：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

输出

算法知识视频讲解

王海波201804220024914

采用回溯法，算个上5步都不操作，绕三个轴的顺逆时针操作一共有7中旋转方法，一共有5步，每一步都有7种选择，递归每一种选择的结果。主要卡再魔方的旋转上面，采用暴力法把每一种旋转处理掉。

#include <stdio.h>

enum
{
    NO_ROATE = 0,
    X_CLOCKWISE,
    X_COUNTERCLOCKWISE,
    Y_CLOCKWISE,
    Y_COUNTERCLOCKWISE,
    Z_CLOCKWISE,
    Z_COUNTERCLOCKWISE,
};

int beautful_degree(int cube_num[6][4])
{
    int total = 0;
    int p = 1;

    for (int i = 0; i < 6; i++)
    {
        for (int j = 0; j < 4; j++)
        {
            p = p * cube_num[i][j];
        }
        total += p;
        p = 1;
    }

    //printf("total = %d\n", total);
    return total;
}

void cube_roate(int cube_num[6][4], int dir)
{
    int a = 0;
    int b = 0;

    if (X_CLOCKWISE == dir)
    {
        a = cube_num[1][0];
        b = cube_num[1][1];
        cube_num[1][0] = cube_num[5][3];
        cube_num[1][1] = cube_num[5][2];
        cube_num[5][3] = cube_num[3][0];
        cube_num[5][2] = cube_num[3][1];
        cube_num[3][0] = cube_num[2][0];
        cube_num[3][1] = cube_num[2][1];
        cube_num[2][0] = a;
        cube_num[2][1] = b;

        //处理另外一面
        a = cube_num[0][0];
        cube_num[0][0] = cube_num[0][1];
        cube_num[0][1] = cube_num[0][3];
        cube_num[0][3] = cube_num[0][2];
        cube_num[0][2] = a;
    }
    else if (X_COUNTERCLOCKWISE == dir)
    {
        a = cube_num[1][0];
        b = cube_num[1][1];
        cube_num[1][1] = cube_num[2][1];
        cube_num[1][0] = cube_num[2][0];
        cube_num[2][0] = cube_num[3][0];
        cube_num[2][1] = cube_num[3][1];
        cube_num[3][0] = cube_num[5][3];
        cube_num[3][1] = cube_num[5][2];
        cube_num[5][2] = b;
        cube_num[5][3] = a;

        //处理另外一面
        a = cube_num[0][0];
        cube_num[0][0] = cube_num[0][2];
        cube_num[0][2] = cube_num[0][3];
        cube_num[0][3] = cube_num[0][1];
        cube_num[0][1] = a;
    }
    else if (Y_CLOCKWISE == dir)
    {
        a = cube_num[0][1];
        b = cube_num[0][3];
        cube_num[0][1] = cube_num[2][1];
        cube_num[0][3] = cube_num[2][3];
        cube_num[2][1] = cube_num[4][1];
        cube_num[2][3] = cube_num[4][3];
        cube_num[4][1] = cube_num[5][1];
        cube_num[4][3] = cube_num[5][3];
        cube_num[5][1] = a;
        cube_num[5][3] = b;

        //处理另外一面
        a = cube_num[3][0];
        cube_num[3][0] = cube_num[3][2];
        cube_num[3][2] = cube_num[3][3];
        cube_num[3][3] = cube_num[3][1];
        cube_num[3][1] = a;
    }
    else if (Y_COUNTERCLOCKWISE == dir)
    {
        a = cube_num[0][1];
        b = cube_num[0][3];
        cube_num[0][3] = cube_num[5][3];
        cube_num[0][1] = cube_num[5][1];
        cube_num[5][1] = cube_num[4][1];
        cube_num[5][3] = cube_num[4][3];
        cube_num[4][1] = cube_num[2][1];
        cube_num[4][3] = cube_num[2][3];
        cube_num[2][1] = a;
        cube_num[2][3] = b;

        //处理另外一面
        a = cube_num[3][0];
        cube_num[3][0] = cube_num[3][1];
        cube_num[3][1] = cube_num[3][3];
        cube_num[3][3] = cube_num[3][2];
        cube_num[3][2] = a;
    }
    else if ( Z_COUNTERCLOCKWISE == dir)
    {
        a = cube_num[0][2];
        b = cube_num[0][3];
        cube_num[0][3] = cube_num[3][2];
        cube_num[0][2] = cube_num[3][0];
        cube_num[3][2] = cube_num[4][0];
        cube_num[3][0] = cube_num[4][1];
        cube_num[4][1] = cube_num[1][3];
        cube_num[4][0] = cube_num[1][1];
        cube_num[1][1] = b;
        cube_num[1][3] = a;

        //处理另外一面
        a = cube_num[2][0];
        cube_num[2][0] = cube_num[2][1];
        cube_num[2][1] = cube_num[2][3];
        cube_num[2][3] = cube_num[2][2];
        cube_num[2][2] = a;
    }
    else if (Z_CLOCKWISE == dir)
    {
        a = cube_num[0][2];
        b = cube_num[0][3];
        cube_num[0][3] = cube_num[1][1];
        cube_num[0][2] = cube_num[1][3];
        cube_num[1][1] = cube_num[4][0];
        cube_num[1][3] = cube_num[4][1];
        cube_num[4][1] = cube_num[3][0];
        cube_num[4][0] = cube_num[3][2];
        cube_num[3][0] = a;
        cube_num[3][2] = b;

        //处理另外一面
        a = cube_num[2][0];
        cube_num[2][0] = cube_num[2][2];
        cube_num[2][2] = cube_num[2][3];
        cube_num[2][3] = cube_num[2][1];
        cube_num[2][1] = a;
    }
}

void n_roate(int cube_num[6][4], int dir)
{
    int op = 0;

    if (X_CLOCKWISE == dir)
    {
        op = X_COUNTERCLOCKWISE;
    }
    else if (X_COUNTERCLOCKWISE == dir)
    {
        op = X_CLOCKWISE;
    }
    else if (Y_CLOCKWISE == dir)
    {
        op = Y_COUNTERCLOCKWISE;
    }
    else if (Y_COUNTERCLOCKWISE == dir)
    {
        op = Y_CLOCKWISE;
    }
    else if (Z_COUNTERCLOCKWISE == dir)
    {
        op = Z_CLOCKWISE;
    }
    else if (Z_CLOCKWISE == dir)
    {
        op = Z_COUNTERCLOCKWISE;
    }
    else
    {
        return;
    }

    cube_roate(cube_num, op);
}

void cubealg(int cube_num[6][4], int step_num, int index, int *max_degree)
{
    int degree = 0;

    degree = beautful_degree(cube_num);
    if (degree > *max_degree)
    {
        *max_degree = degree;
    }

    if(index < step_num)
    {
        //有7中操作方法
        for (int i = 0; i < 7; i++)
        {
            cube_roate(cube_num, i);
            cubealg(cube_num, step_num, index + 1, max_degree);

            //还原旋转操作
            n_roate(cube_num, i);
        }
    }
}

void test_cube(int argc, char **args)
{
    int argv[25] = { 0 };
    int cube_num[6][4] = {0};

    for (int i = 0; i < 24; i++)
    {
        scanf("%d", &argv[i]);
    }

    cube_num[0][0] = argv[0];
    cube_num[0][1] = argv[1];
    cube_num[0][2] = argv[2];
    cube_num[0][3] = argv[3];

    cube_num[1][0] = argv[4];
    cube_num[1][1] = argv[5];
    cube_num[1][2] = argv[10];
    cube_num[1][3] = argv[11];

    cube_num[2][0] = argv[6];
    cube_num[2][1] = argv[7];
    cube_num[2][2] = argv[12];
    cube_num[2][3] = argv[13];

    cube_num[3][0] = argv[8];
    cube_num[3][1] = argv[9];
    cube_num[3][2] = argv[14];
    cube_num[3][3] = argv[15];

    cube_num[4][0] = argv[16];
    cube_num[4][1] = argv[17];
    cube_num[4][2] = argv[18];
    cube_num[4][3] = argv[19];

    cube_num[5][0] = argv[20];
    cube_num[5][1] = argv[21];
    cube_num[5][2] = argv[22];
    cube_num[5][3] = argv[23];

    int max_degree = 0;

    cubealg(cube_num, 5, 0, &max_degree);

    printf("%d\n", max_degree);
}

int main(int argc, char** argv)
{
    test_cube(argc, argv);

    return 0;
}

发表于 2022-03-03 21:24:35 回复(0)