2010年8月25日 星期三

197 - Cube

由27個小方塊組合而成的3x3x3方塊被拆解成下面七個部份:

Figure 1: 組成3x3x3方塊的七種結構
\begin{figure}\begin{center} \mbox{} \epsfbox{p197a.eps}\end{center}\end{figure}

這七種結構可以以許多種不同的方式重新組合成3x3x3的大方塊,下圖顯示有兩種組合方式。上面三張圖與下面三張圖分別表示一種方塊的組成方式,左圖表示方塊的第一層,中間為方塊的第二層,右圖為方塊的第三層,每一張圖有9個字母,表示在這9個位置上分別為七種結構中的一種,這七種結構的代號如上圖所示,為a~g。

Figure 2: 兩種可能的組合方式
\begin{figure}\begin{center} \begin{tabular}{\vert ccc\vert c\vert ccc\vert c\ve... ...c \\ \cline{1-3} \cline{5-7} \cline{9-11} \end{tabular}\end{center}\end{figure}

請你寫一個程式輸出所有可能的組合方式,但若僅僅透過旋轉的方式由一種組合產生另一種組合,則不輸出此種重複的組合。


Hint: 結構 a 是所有七種結構中唯一一種不能經由旋轉或平移後還能變回自已原來樣子的結構,為了避免產生出與其他組合方式相同的解(僅僅只是角度不同),你可以限定 a 結構只能平移而不能旋轉,這樣可避免產生出相同的解。

Input

輸入會有多組測試資料,每一組測試資會指定 a 結構的初始位置,你可以對a作平移,但決不能旋轉它。

Output

對每一個找到的組合,請輸出一列以字串表示的組合結構,字串是用來表示方塊組成結構的線性表示法,每一個字元代表佔據在該位置上的七種可能結構之一,請照下列方式輸出字串:
  • 整個字串由三個子字串組成,分別為第一層、第二層、第三層。
  • 每個子字串又分別由三個子字串所組成,分別為上列、中列、下列。
  • 列字串由三個字元組成,分別表示左邊、中間,與右邊的小方塊。
Figure 2 的字串表示式如下:
adcaccaacddgbfgffedggbfebee
aababbadcffegfcddcfeeggedgc 

按照a~g的七種結構命名方式來表示上述的方塊表示式對你的程式來說應該會是較好的選擇。

在每組測試資料之後輸出一個空行。

Figure 3: 方塊與字串位置的對應關係
\begin{figure}\begin{center} \mbox{} \epsfbox{p197b.eps}\end{center}\end{figure}

上圖顯示各個字元對應到小方塊的位置。

Sample input

aa.a..a....................
.........a..a..aa..........

Sample output

aababbadcggeffcddcgeegfedfc
aababbadceffgdcgdceefedfggc
...
aababbadcffegfcddcfeeggedgc

adcaccaacfddfebgeeffdggbgeb
...

原文出處

沒有留言:

張貼留言