2013年7月18日 星期四

12291 - Polyomino Composer



  Polyomino Composer 

A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge.
- Wikipedia
在七巧拼圖遊戲中, 通常會是三角形的拼圖,而 polyomino 則專指用正方形連接起的幾何圖形,給一個大的 polyomino 以及小的 polyomino,能否用兩個小的 polyomino 拼出大的,而且小的 polyomino 不能經過翻轉或旋轉,同時也不能重疊。

最左邊的圖中,可以看到有一種方法可以組成大的 polyomino,但是右邊兩張圖則不行。
在中間的圖形中,發生其中一塊發生旋轉,而最右邊的則是兩個都發生旋轉,因此都是不行的。




Input 

最多 20 筆測資,每組測資有兩個整數 n, m (1 <= m <= n <= 10),接下來會有 n 行描述大的 polyomino,每一行確切只會有 n 個由 '*' 或 '.' 組成,接下來則會有 m 行描述小的 polyomino,每一行確切只會有 m 個由 '*' 或 '.' 組成。

合法的 polyomino 一定至少包含一個正方形,程式終止於 n = m = 0

Output 

對於每組測資,如果可以由兩個拼成,則輸出 1,反之則輸出 0。

Sample Input 

4 3
.**.
****
.**.
....
**.
.**
...
3 3
***
*.*
***
*..
*..
**.
4 2
****
....
....
....
*.
*.
0 0

Sample Output 

1
0
0



The Seventh Hunan Collegiate Programming Contest
Problemsetter: Rujia Liu, Special Thanks: Yiming Li & Jane Alam Jan