466 - Mirror, Mirror

一個 n x n 的圖形由 "." 與 "X" 所組成，本題給你原始的圖形與經過轉換後的圖形，請你判斷是否可經由特定的轉換步驟使原圖轉換成另一張圖。轉換步驟有下列幾種：

旋轉90度(90 Degree Rotation)：向右旋轉90度。
旋轉180度(180 Degree Rotation)：向右旋轉180度。
旋轉270度(270 Degree Rotation)：向右旋轉270度。
垂直映射(Vertical Reflection)：以一條水平線為中心作上下的鏡像映射。
組合式(Combination)：垂直映射後再作旋轉。
一致(Preservation)：轉換後的圖與原圖相同。
無解(Improper)：無法經由上述轉換得到新圖。

Input

輸入會有多組測試資料，每組資料的第一列有一個整數 n (1 <= n <= 10)表示接下來有兩個 n x n 的圖形，兩個圖形並排出現，並以一個空白字元隔開，左邊為原圖，右邊為轉換後的圖形，圖形僅由"."與"X"組成。

Output

請輸出由原圖轉換成新圖的步驟，並請輸出測試資料的編號(由1開始)。必須輸出其「最簡」步驟，旋轉比垂直映射還簡單，角度小的旋轉比角度大的旋轉還簡單，不作任何步驟轉換當然會是最簡單的。

所有可能的步驟已列在上面，也就是說，並不會有「旋轉360度」的步驟，也沒有「水平映射」的步驟。當旋轉或垂直映射都不行的話，請再考慮先作垂直映射再作旋轉的組合步驟，反過來說，如果單一步驟可行的話，你就不應該考慮組合步驟。輸出資料請參考範例輸出。

Sample Input

5
X...X ....X 
.X... ...X.
...X. .X...
..X.X ..X..
....X XX..X
6
....XX X....X
...X.. X.X...
XX..X. .X..X.
..X... ...X.X
...X.. ..X...
..X..X ..X...
2
X. X.
.X .X
4 
..X. ...X
XX.. ....
.... XX..
...X ..X.
5
X.... .X...
.X... ..X..
.X... ..X..
...X. ....X
....X X....
4
.X.. ..X.
.X.X X...
.... ..XX
..X. ....
2
.. XX
XX ..

Sample Output

Pattern 1 was rotated 90 degrees.
Pattern 2 was rotated 270 degrees.
Pattern 3 was preserved.
Pattern 4 was reflected vertically.
Pattern 5 was improperly transformed.
Pattern 6 was reflected vertically and rotated 270 degrees.
Pattern 7 was rotated 180 degrees.
原文出處