1436 . 益智拼盤
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 1
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
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 1
11155666
11155556
12333556
12333666
22233788
22277788
44477788
44444788
111
321
222
11155556
12333556
12333666
22233788
22277788
44477788
44444788
111
321
222
Hints
Problem Source
原TIOJ1436 / 2004NPSC初賽(prob F)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 33 |
| 2 | 1 | 33 |
| 3 | 2 | 34 |