TopCoder

Thumb 100
$SCJ$
$SCJ$

User's AC Ratio

66.7% (6/9)

Submission's AC Ratio

43.3% (13/30)

Description

  又到了機器人大賽的時間。為了讓自己設計的機器人能在大賽中獲得評審的青睞,參賽者無不攪盡腦汁,讓自己的機器人能有最特殊的功能。

  身為拼圖迷的你最希望的就是做出能跟人比賽拼圖的機器人了。但是你很快地發現,讓機器人能判斷兩片拼圖上的圖案是否連續實在是件很困難的事情。所幸,機器人可以準確地分析拼圖四面的角或是缺口。縱使機器人無法辨別兩片拼圖的圖案是否連續,但一片拼圖的一個角能不能搭上另一片拼圖的一個缺口,機器人卻可以輕鬆判斷。憑藉著辨別拼圖的角和缺口的能力,你設計的機器人是否能和人一樣完成一幅拼圖呢?

Input Format

輸入檔包含多筆的測試資料。

每一筆測試資料的第一行有兩個數字r c (1 ≤ r*c ≤ 252),分別表示拼圖的上到下的高一共是r片拼圖,左到右的寛度是c片拼圖。接下來一共有r*c行,每一行有8個字元,表示一片拼圖的資訊。前4個字元依序表示拼圖的左﹑上﹑右﹑下邊。大寫字母表示該邊為角,小寫字母表示該邊為缺口,一個減號則表示該邊是平的(表示這片拼圖是邊框中的其中一塊)。字母相同的角可以和缺口相接:例如1片拼圖的右側為A,另一片的左側為a,則兩片拼圖可以左右相接。

後4個字元則表示拼圖的圖案,圖案除了英文字母外也可能是空白字元。旋轉一片拼圖後,拼圖上的圖案看起來是不一樣的。因此4個字元分別表示拼圖四個方向的圖案。如果拼圖不需要旋轉,則該片拼圖的圖案即是後4個字元中的第1個。若拼圖需要逆時針旋轉90度,則拼上拼圖的圖案則是第2個,再旋轉90度則是第3個,餘以類推。

第一片拼圖(每筆測試資料的第二行)一定剛好是最左上角的拼圖,其他拼圖的順序則不固定。你的機器人可以從第一片拼圖開始往後拼完整幅拼圖。除了第一片拼圖以外,其他拼圖可能需要先經過旋轉才能拼上去。為了讓大家清楚了解拼圖的表示法,下方的範例輸入資料第一筆為一個未被打亂的拼圖,拼圖的次序由左到右,由上到下。

當測試資料輸入的r和c皆為0時表示輸入檔結束,程式不需要對這一行輸入作處理。

Output Format

對於每一筆測試資料,請將拼好的拼圖圖案輸出。每幅拼圖之後請輸出一個空行來作分隔。(你可以假設每幅拼圖只有一種拼法能完全拼圖。)

Sample Input

3 3
--CBOHPY
c-ccOX Y
C--AOCIG
-bbbOO O
BCaB WA
Aa-BOTTU
-Ba-OEDA
AbA-OZRI
ab--ODRT
6 4
--wZXXKC
W-JC PGP
-JUPUDCG
tuTkYT R
WJtmRW I
Tw-IDPNP
jtKCYGAD
-wRlXFPN
Ty-WDXFE
NrFTG KN
teqJZC R
buVMXJOJ
-znW BJB
LRg-AQCD
--WlK KR
fNcBVXME
w-GQDDBC
Ej-LKQKD
--CSZBZX
Uj-sW NZ
wv-YXO O
c-VvOLU
rncjDM T
pi-- HVW
0 0

Sample Output

OOO
O O
OOO

X  X
 XX 
X  X
DDDD
D  D
 DD 

Hints

※2007/10/07: 題目修正「逆時針」,感謝seanwu大大。

Problem Source

原TIOJ1038 / NPSC2003初賽(prob A)

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 15000 65536 65536