TopCoder

User's AC Ratio

100.0% (1/1)

Submission's AC Ratio

100.0% (1/1)

Description

相信大家小時候都玩過益智拼盤吧!這個遊戲是這樣玩的,在一個N乘N的矩形上,分割成很多塊形狀不同的拼圖,把拼圖打散以後,拼回原來的矩形裡就是這個遊戲的目的。

例如下面的拼圖:


111 22 333 444 55 666 7 88
111 2222 333 44444 5555 6 777 88
1 22 33 55 6 777 88
1 666 7 88

可以拼成一個8乘8的矩形如下:
11155666
11155556
12333556
12333666
22233788
22277788
44477788
44444788

你的工作就是寫一個程式把輸入的拼圖塊拼成一個N乘N的矩形。提示:每塊拼圖都可以自由的旋轉90度,180度,270度;不過為了簡化題目,所以你可以假定不需要把拼圖左右鏡射。例:

444             44      44444       4                444
44444 可轉成 44 或 444 或 4 但不能變成 44444
44 44
4 44
4 44

Input Format

輸入檔會有好幾組資料,每組資料的第一行有二個整數 N M 以一個空白格開(2 ≤ N ≤ 20),(2≤M≤9), N代表矩形的大小,M代表拼圖有幾塊。接下來會有好幾行表示拼圖的圖案,第1塊拼圖,第2塊拼圖… 第M塊拼圖會依序出現,中當第M個拼圖輸入完以後,這組資料就結束。

每塊拼圖的輸入分別是這樣的,對第i塊拼圖來說,會用數字i來代表這塊屬於拼圖的部份,其他部分則是以0表示;首先會有一行有兩個正整數Xi Yi,用空白格開,代表這塊拼圖是在Xi乘Yi的格子裡,接下來會有Xi行輸入,每行長Yi,代表行輸入就是這塊拼圖的外形,你可以假設每塊拼圖都是完整的不會碎裂成好幾塊,且每塊拼圖都至少會有一部分貼在一行的最左邊。

最後如果N M是0 0的話,就代表所有的輸入結束。

Output Format

對每組輸入資料,請把拼好的N乘N矩形輸出,後面再多加上一行空行。輸入資料裡的拼圖只會有一種拼法可以拼成N乘N的矩形,但是因為旋轉的關係,可能會變成4種,請你輸出最小的那種﹝至少會有一種方法可以拼成N乘N的矩形﹞。

在每組拼圖後面請多空一行。

一個拼圖的大小怎麼判斷呢?我們可以把一個拼圖當成一個很長的正整數依序寫成的,例如拼圖
111
321
222
可以看成是111321222這個數字,因此這個雖然拼圖還可以旋轉成

112         222        231
122 或 123 或 221
132 111 211

但我們要輸出的還是數字最小的
111
321
222

Sample Input

8 8
4 3
111
111
100
100
3 4
2200
2222
2200
3 3
333
333
033
2 5
44400
44444
3 4
5500
5555
0055
4 3
666
006
006
666
4 3
007
777
777
007
4 2
88
88
88
88
3 3
2 3
111
001
2 3
222
020
1 1
3
0 0

Sample Output

11155666
11155556
12333556
12333666
22233788
22277788
44477788
44444788

111
321
222

Hints

Problem Source

原TIOJ1436 / 2004NPSC初賽(prob F)

Subtasks

For Testdata: 0 ~ 0, Score: 33
For Testdata: 1 ~ 1, Score: 33
For Testdata: 2 ~ 2, Score: 34
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 10000 65536 262144
1 10000 65536 262144
2 10000 65536 262144