蓝桥杯-2017-魔方状态-python3

标题：魔方状态

二阶魔方就是只有2层的魔方，只由8个小块组成。如图p1.png所示。

小明很淘气，他只喜欢3种颜色，所有把家里的二阶魔方重新涂了颜色，如下：

前面：橙色

右面：绿色

上面：黄色

左面：绿色

下面：橙色

后面：黄色

请你计算一下，这样的魔方被打乱后，一共有多少种不同的状态。

如果两个状态经过魔方的整体旋转后，各个面的颜色都一致，则认为是同一状态。

请提交表示状态数的整数，不要填写任何多余内容或说明文字。

解法一：Python官方解法，仿自博主豌豆苞谷

import copy
import sys  
sys.setrecursionlimit(10000000)  # 手动修改深度
from collections import dequest = set()
que = deque()  # 队列，用于实现广度优先搜索be = ["oybbgb", "oygbbb", "bygbby", "bybbgy", "obbogb", "obgobb", "bbgoby", "bbbogy"]
be = [list(be[i]) for i in range(len(be))]# 单个小块旋转
def ucell(a):a[0], a[2] = a[2], a[0]a[2], a[5] = a[5], a[2]a[5], a[4] = a[4], a[5]returndef rcell(a):a[1], a[0] = a[0], a[1]a[0], a[3] = a[3], a[0]a[3], a[5] = a[5], a[3]returndef fcell(a):a[2], a[1] = a[1], a[2]a[1], a[4] = a[4], a[1]a[4], a[3] = a[3], a[4]return# 魔方旋转
def u(s):ucell(s[0])ucell(s[1])ucell(s[2])ucell(s[3])s[1], s[0] = s[0], s[1]s[2], s[1] = s[1], s[2]s[3], s[2] = s[2], s[3]returndef f(s):fcell(s[0])fcell(s[1])fcell(s[4])fcell(s[5])s[1], s[5] = s[5], s[1]s[0], s[1] = s[1], s[0]s[4], s[0] = s[0], s[4]returndef r(s):rcell(s[1])rcell(s[2])rcell(s[6])rcell(s[5])s[2], s[1] = s[1], s[2]s[5], s[1] = s[1], s[5]s[6], s[5] = s[5], s[6]return# 观看角度
def uwhole(s):u(s)ucell(s[4])ucell(s[5])ucell(s[6])ucell(s[7])s[5], s[4] = s[4], s[5]s[6], s[5] = s[5], s[6]s[7], s[6] = s[6], s[7]returndef fwhole(s):f(s)fcell(s[2])fcell(s[6])fcell(s[7])fcell(s[3])s[2], s[6] = s[6], s[2]s[3], s[2] = s[2], s[3]s[7], s[3] = s[3], s[7]returndef rwhole(s):r(s)rcell(s[0])rcell(s[3])rcell(s[4])rcell(s[7])s[3], s[7] = s[7], s[3]s[0], s[3] = s[3], s[0]s[4], s[0] = s[0], s[4]returndef convert(s):tmp = copy.deepcopy(s)tmp = [''.join(s[i]) for i in range(len(s))]tmp = ''.join(tmp)return tmpdef to_list(x):x = [x[i:i + 6] for i in range(0, len(x), 6)]x = [list(x[i]) for i in range(len(x))]return xdef try_to_insert(s):   # 去重s0 = copy.deepcopy(s)for i in range(4):fwhole(s0)for j in range(4):uwhole(s0)for k in range(4):rwhole(s0)if convert(s0) in st:return Falsest.add(convert(s))return Trueif __name__ == '__main__':que.append(convert(be))st.add(convert(be))while len(que) != 0:t = que.popleft()  # 字符串t0 = to_list(t)for i in range(3):tmp = copy.deepcopy(t0)if i == 0:u(tmp)elif i == 1:r(tmp)elif i == 2:f(tmp)if (try_to_insert(tmp)):que.append(convert((tmp)))print(len(st))

 解法二：

from functools import reducedef f(n):return reduce(lambda x, y: x * y, range(1, n + 1))if __name__ == '__main__':s1 = f(8) * 3 ** 8 / 16s2 = 3 * f(4) * 3 ** 4s3 = 6 * f(4) * 3 ** 4print(((s1 + s2 + s3) // 24) // 3)

提供一个c++解法来自博主豌豆苞谷：

#include 
using namespace std;
typedef char st[8][7];
st state[2000000];
set all;
st begin={{"oybbgb"},{"oygbbb"},{"bygbby"},{"bybbgy"},{"obbogb"},{"obgobb"},{"bbgoby"},{"bbbogy"}}; 
//st begin={{"oooooo"},{"oooooo"},{"oooooo"},{"oooooo"},{"oooooo"},{"oooooo"},{"oooooo"},{"oooooo"}};
//只有一个颜色的魔方 ans=1 
//st begin={{"rykkbk"},{"rygkkk"},{"kygkko"},{"kykkbo"},{"rkkwbk"},{"rkgwkk"},{"kkgwko"},{"kkkwbo"}};
//正常2阶魔方状态  r红 y黄 b蓝 g绿 w白 o橙  k黑(红对橙，白对黄，蓝对绿，颜色相近的相对)这里白为底 前为红
//需要将state大小改为4000000
//这个测试用例跑了20分钟左右 560M内存  ans=3674160 与实际二阶魔方状态数相同 见下截图 
int front, tail;
void ucell(char *a){swap(a[0], a[2]); swap(a[2], a[5]); swap(a[5], a[4]);}
void rcell(char *a){swap(a[1], a[0]); swap(a[0], a[3]); swap(a[3], a[5]);}
void fcell(char *a){swap(a[2], a[1]); swap(a[1], a[4]); swap(a[4], a[3]);}
void u(st &s)//顶层顺时针旋转 
{ucell(s[0]);ucell(s[1]);ucell(s[2]);ucell(s[3]);swap(s[1], s[0]);swap(s[2], s[1]);swap(s[3], s[2]);
}
void uwhole(st &s)//整个魔方从顶部看 顺时针转 用于判重 
{u(s);ucell(s[4]);ucell(s[5]);ucell(s[6]);ucell(s[7]);swap(s[5], s[4]);swap(s[6], s[5]);swap(s[7], s[6]);
}
void f(st &s)//前面一层 顺时针转 
{fcell(s[0]);fcell(s[1]);fcell(s[4]);fcell(s[5]);swap(s[1], s[5]);swap(s[0], s[1]);swap(s[4], s[0]);
}
void fwhole(st &s)//整个魔方从前面看 顺时针转 用于判重 
{f(s);fcell(s[2]);fcell(s[6]);fcell(s[7]);fcell(s[3]);swap(s[2], s[6]);swap(s[3], s[2]);swap(s[7], s[3]);
}
void r(st &s)//魔方右层顺时针转 
{rcell(s[1]);rcell(s[2]);rcell(s[6]);rcell(s[5]);swap(s[2], s[1]);swap(s[5], s[1]);swap(s[6], s[5]);
}
void rwhole(st &s)//整个魔方从右边看 顺时针转 用于判重 
{r(s);rcell(s[0]);rcell(s[3]);rcell(s[4]);rcell(s[7]);swap(s[3], s[7]);swap(s[0], s[3]);swap(s[4], s[0]);
}
string convert(st &s)//魔方状态二维字符数组 转化为string 
{string ss;for(int i=0; i<8; i++)ss+=s[i];return ss;
}
bool try_to_insert(int tail)//判重 
{st k;memcpy((void*)k, (void*)state[tail], sizeof(state[tail]));for(int i=0; i<4; i++){fwhole(k);for(int j=0; j<4; j++){uwhole(k);for(int q=0; q<4; q++){rwhole(k);if(all.count(convert(k))==1){return false;}}}}all.insert(convert(k));return true;
}
int main()
{front=0,tail=1;all.insert(convert(begin));memcpy((void*)state[0],(void*)begin,sizeof(begin));while(front!=tail){//对当前状态分别模拟三种操作U R F 然后判重 for(int i=0; i<3; i++){memcpy((void*)state[tail], (void*)state[front], sizeof(state[front]));if(i==0){u(state[tail]);if(try_to_insert(tail))tail++;}else if(i==1){r(state[tail]);if(try_to_insert(tail))tail++;}else if(i==2){f(state[tail]);if(try_to_insert(tail))tail++;}}front++;}cout<

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