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