2017年第八屆藍(lán)橋杯 - 省賽 - C/C++大學(xué)A組 - C. 魔方狀態(tài)

魔方狀態(tài)

二階魔方就是只有2層的魔方，只由8個(gè)小塊組成。

小明很淘氣，他只喜歡3種顏色，所有把家里的二階魔方重新涂了顏色，如下：

前面：橙色
右面：綠色
上面：黃色
左面：綠色
下面：橙色
后面：黃色

請(qǐng)你計(jì)算一下，這樣的魔方被打亂后，一共有多少種不同的狀態(tài)。

如果兩個(gè)狀態(tài)經(jīng)過(guò)魔方的整體旋轉(zhuǎn)后，各個(gè)面的顏色都一致，則認(rèn)為是同一狀態(tài)。

請(qǐng)?zhí)峤槐硎緺顟B(tài)數(shù)的整數(shù)，不要填寫(xiě)任何多余內(nèi)容或說(shuō)明文字。

Ideas

這道題相對(duì)來(lái)說(shuō)比較麻煩，而且比賽的時(shí)候放在第三題，有點(diǎn)恐怖，建議如果比賽的時(shí)候遇到這種填空題，20分鐘解決不出來(lái)就跳過(guò)吧。

如果想要解決這道題，首先面臨的第一個(gè)問(wèn)題就是，魔方是三維，我們?cè)趺从糜?jì)算機(jī)語(yǔ)言進(jìn)行表示。

二階魔方是由八個(gè)塊組成的，我們先給這8個(gè)塊進(jìn)行編號(hào)，上面四個(gè)塊編號(hào)為0_{3，下面四個(gè)塊編號(hào)為4}7。

然后對(duì)于每一個(gè)塊，都有六個(gè)面，其中有三個(gè)面是有顏色，另外三個(gè)面在魔方內(nèi)部，是看不見(jiàn)的，所以我們還要對(duì)每一個(gè)面進(jìn)行編號(hào)。

編號(hào)為0的塊，它的6個(gè)面可以表示為['o', 'y', 'x', 'x', 'g', 'x']，其中o表示橙色，y表示黃色，g表示綠色，x表示看不見(jiàn)。

接下來(lái)我們就可以用一個(gè)二維字符數(shù)組表示一個(gè)二階魔方：

cube = [['o', 'y', 'x', 'x', 'g', 'x'],['o', 'y', 'g', 'x', 'x', 'x'],['x', 'y', 'g', 'x', 'x', 'y'],['x', 'y', 'x', 'x', 'g', 'y'],['o', 'x', 'x', 'o', 'g', 'x'],['o', 'x', 'g', 'o', 'x', 'x'],['x', 'x', 'g', 'o', 'x', 'y'],['x', 'x', 'x', 'o', 'g', 'y']]

魔方的狀態(tài)表示完了之后，接下來(lái)就要轉(zhuǎn)動(dòng)，進(jìn)行狀態(tài)轉(zhuǎn)移。

玩過(guò)魔方的應(yīng)該都知道，它的狀態(tài)轉(zhuǎn)移其實(shí)只需要通過(guò)三種旋轉(zhuǎn)就可以達(dá)到：上面旋轉(zhuǎn)（U）、右面旋轉(zhuǎn)（R）、前面旋轉(zhuǎn)（F）。

假如對(duì)于上面旋轉(zhuǎn)（U）操作，首先0、1、2、3四個(gè)塊的位置要交換。

0 -> 3 3 -> 2 2 -> 1 1 -> 0

然后每個(gè)塊的6個(gè)面編碼也要變換：

0 -> 4 4 -> 5 5 -> 2 2 -> 0

同理我們可以得出剩下兩種旋轉(zhuǎn)對(duì)應(yīng)的塊和面的變換，這樣我們就得到了魔方狀態(tài)轉(zhuǎn)移的步驟。

接下來(lái)我們就要進(jìn)行搜索了，得到魔方的所有狀態(tài)。

對(duì)于某一種狀態(tài)，它有R、U、F三種操作，通過(guò)每一種操作可以得到一個(gè)新的狀態(tài)，而對(duì)于每一種狀態(tài)，要判斷一下之前有沒(méi)有出現(xiàn)過(guò)，如果沒(méi)有，添加到狀態(tài)集合中，并且后面要基于這種狀態(tài)繼續(xù)搜索。

所以這類(lèi)似于一個(gè)BFS的問(wèn)題，我們需要通過(guò)隊(duì)列來(lái)輔助實(shí)現(xiàn)。

另外題目中說(shuō)“如果兩個(gè)狀態(tài)經(jīng)過(guò)魔方的整體旋轉(zhuǎn)后，各個(gè)面的顏色都一致，則認(rèn)為是同一狀態(tài)”，其實(shí)就是我們進(jìn)行去重的依據(jù)，還需要定義一個(gè)輔助函數(shù)進(jìn)行魔方的整體旋轉(zhuǎn)。

定義函數(shù)try_add，傳入一個(gè)魔方的狀態(tài)，然后進(jìn)行整體旋轉(zhuǎn)操作，同樣類(lèi)似于面的旋轉(zhuǎn)操作，不同的是三個(gè)面都要進(jìn)行整體旋轉(zhuǎn)。

Code

Python

from collections import deque from copy import deepcopydef process_cube(state) -> str:return ''.join([''.join(x) for x in state])def u(state):# 上面順時(shí)針旋轉(zhuǎn)一次def u_cell(cell):# 上面順時(shí)針旋轉(zhuǎn)一次對(duì)應(yīng)的每個(gè)塊的面編碼變化cell[4], cell[5], cell[2], cell[0] = cell[0], cell[4], cell[5], cell[2]for i in [0, 1, 2, 3]:u_cell(state[i])state[0], state[1], state[2], state[3] = state[1], state[2], state[3], state[0]return statedef r(state):# 右面順時(shí)針旋轉(zhuǎn)一次def r_cell(cell):# 右面順時(shí)針旋轉(zhuǎn)一次對(duì)應(yīng)的每個(gè)塊的面編碼變化cell[0], cell[1], cell[5], cell[3] = cell[3], cell[0], cell[1], cell[5]for i in [1, 2, 5, 6]:r_cell(state[i])state[1], state[2], state[5], state[6] = state[5], state[1], state[6], state[2]return statedef f(state):# 前面順時(shí)針旋轉(zhuǎn)一次def f_cell(cell):# 前面順時(shí)針旋轉(zhuǎn)一次對(duì)應(yīng)的每個(gè)塊的面編碼變化cell[1], cell[2], cell[3], cell[4] = cell[4], cell[1], cell[2], cell[3]for i in [0, 1, 4, 5]:f_cell(state[i])state[0], state[1], state[4], state[5] = state[4], state[0], state[5], state[1]return statedef u_whole(state):# 上+下面順時(shí)針旋轉(zhuǎn)一次def u_d_cell(cell):# 上+下面順時(shí)針旋轉(zhuǎn)一次對(duì)應(yīng)的每個(gè)塊的面編碼變化cell[4], cell[5], cell[2], cell[0] = cell[0], cell[4], cell[5], cell[2]for i in range(8):u_d_cell(state[i])state[0], state[1], state[2], state[3] = state[1], state[2], state[3], state[0]state[4], state[5], state[6], state[7] = state[5], state[6], state[7], state[4]return statedef r_whole(state):# 右+左面順時(shí)針旋轉(zhuǎn)一次def r_l_cell(cell):# 右+左面順時(shí)針旋轉(zhuǎn)一次對(duì)應(yīng)的每個(gè)塊的面編碼變化cell[0], cell[1], cell[5], cell[3] = cell[3], cell[0], cell[1], cell[5]for i in range(8):r_l_cell(state[i])state[1], state[2], state[5], state[6] = state[5], state[1], state[6], state[2]state[0], state[3], state[4], state[7] = state[4], state[0], state[7], state[3]return statedef f_whole(state):# 前+后面順時(shí)針旋轉(zhuǎn)一次def f_b_cell(cell):# 前+后面順時(shí)針旋轉(zhuǎn)一次對(duì)應(yīng)的每個(gè)塊的面編碼變化cell[1], cell[2], cell[3], cell[4] = cell[4], cell[1], cell[2], cell[3]for i in range(8):f_b_cell(state[i])state[0], state[1], state[4], state[5] = state[4], state[0], state[5], state[1]state[3], state[2], state[7], state[6] = state[7], state[3], state[6], state[2]return statedef try_add(state):for _ in range(4):state = u_whole(deepcopy(state))for _ in range(4):state = r_whole(deepcopy(state))for _ in range(4):state = f_whole(deepcopy(state))if process_cube(state) in states:returnstates.add(process_cube(state))queue.append(state)if __name__ == '__main__':cube = [['o', 'y', 'x', 'x', 'g', 'x'],['o', 'y', 'g', 'x', 'x', 'x'],['x', 'y', 'g', 'x', 'x', 'y'],['x', 'y', 'x', 'x', 'g', 'y'],['o', 'x', 'x', 'o', 'g', 'x'],['o', 'x', 'g', 'o', 'x', 'x'],['x', 'x', 'g', 'o', 'x', 'y'],['x', 'x', 'x', 'o', 'g', 'y']]queue, states = deque(), set()queue.append(cube)states.add(process_cube(cube))while queue:front = queue.popleft()u_state = u(deepcopy(front))try_add(u_state)r_state = r(deepcopy(front))try_add(r_state)f_state = f(deepcopy(front))try_add(f_state)print(len(states))

Answer: 229878

與50位技術(shù)專(zhuān)家面對(duì)面20年技術(shù)見(jiàn)證，附贈(zèng)技術(shù)全景圖

總結(jié)

以上是生活随笔為你收集整理的2017年第八届蓝桥杯 - 省赛 - C/C++大学A组 - C. 魔方状态的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。