标签搜索

目 录CONTENT

文章目录

字节--旋转魔方.md

小小城
2021-08-22 / 0 评论 / 0 点赞 / 7 阅读 / 2,369 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2022-05-02,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

字节--旋转魔方

@[toc]

一、题目描述

二阶魔方又叫小魔方,是222的立方形结构。每一面都有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

输出例子1:
8281

二、分析

这道题很多人一看题就有思路,这不就是一个搜索问题嘛,无非就是(顺时针、逆时针)和(上下左右前后六个面)的组合情况嘛,但是难就难在怎么把每种旋转给表示出来,用什么数据结构而已

  •  静下心来仔细这道题目,其实也不难,只是过程很繁琐,就是bfs搜索解决,核心是怎么将魔方旋转时魔方方块的位置变动表达出来,解决这个剩下的就很好办了。
  •  这里魔方直接用一个数组vec保存,假设魔方底面右旋一次,对应位置变换
    在这里插入图片描述
  •  同样,每一面的右旋都可以求出位置变换矩阵来,剩下的就是dfs求解的过程了。
  •  为了方便,我们只考虑魔方逆时针的旋转情况,因为顺时针可以用逆时针旋转3次模拟出来

三、代码

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

const int n = 24;

//六个面在经过一次逆时针旋转后的位置变化情况,可以画图验证
const int Rotate[6][24] = 
{
	//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}
};

//魔方6个面的位置坐标
const int side[6][4] = 
{
	{0, 1, 2, 3},
	{4, 5, 10, 11},
	{6, 7, 12, 13},
	{8, 9, 14, 15},
	{16, 17, 18, 19},
	{20,21, 22, 23}
};

//旋转操作
//vec就代表魔方,用数组表示
//i代表旋转那个面
void rotateRC(vector<int>& vec, int i)
{
	//拷贝一份
	vector<int> tmp(vec);
 
 	//根据i,把旋转完成后的面重新赋值给vec
 	//n为24,相当于把旋转后的内容给了vec
	for (int j = 0; j < n; ++j)
	{
		//Rotate[i][j]:i代表旋转那个面,定位在Rotate数组的那个位置
		//找到正确的位置直接赋值即可
		vec[j] = tmp[Rotate[i][j]];
	}
	tmp.clear();
}

//求整个魔方的优美度
long long getArea(const vector<int>& vec)
{
	long long sum = 0, mul = 1;
	for (int i = 0; i < 6; ++i)
	{
		for (int j = 0; j < 4; ++j)
		{
			mul *= vec[side[i][j]];
		}
		sum += mul;
		mul = 1;
	}
	return sum;
}

//搜索
long long dfs(vector<int> vec, int count)
{
	//获取当前魔方状态的优美度并保存
	long long ans = getArea(vec);

	//判断操作次数
	if (0 == count)	
		return ans;

	//用i分别模拟待旋转的6个面
	for (int i = 0; i < 6; ++i)
	{
		vector<int> tmp(vec);
		
		//代表逆时针旋转一次
		rotateRC(tmp, i);
		//在旋转一次的基础上递归
		ans = max(ans, dfs(tmp, count - 1));
		//顺时针旋转(逆时针旋转3次相当于顺时针旋转1次)
		rotateRC(tmp, i);
		rotateRC(tmp, i);
		//在顺时针旋转的基础上递归
		ans = max(ans, dfs(tmp, count - 1));
	}
	return ans;
}
int main()
{
	vector<int> vec(n);
	for (int i = 0; i < n; ++i)
		cin >> vec[i];
	
	//dfs搜索
	cout << dfs(vec, 5) << endl;
	system("pause");
	return 0;
}
  •  总之发现这道题并不难,重点是怎么表示‘旋转’而已
0

评论区