Polyomino Composer
Polyomino Composer |
A polyomino is a plane geometric figure formed by joining one or more equal squares edge to edge.在七巧拼圖遊戲中, 通常會是三角形的拼圖,而 polyomino 則專指用正方形連接起的幾何圖形,給一個大的 polyomino 以及小的 polyomino,能否用兩個小的 polyomino 拼出大的,而且小的 polyomino 不能經過翻轉或旋轉,同時也不能重疊。- Wikipedia
最左邊的圖中,可以看到有一種方法可以組成大的 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
沒有留言:
張貼留言