多联骨牌

题目描述

多联骨牌（polyomino）是由若干个小正方形沿边拼接而成的连通多边形拼图块。

有一个四行四列的网格，以及三个能放进该网格的多联骨牌。

第 $i$ 个多联骨牌的形状由 $16$ 个字符 $P_{i,j,k}$ $(1 \le j, k \le 4)$ 表示。它们描述的是将第 $i$ 个多联骨牌放入网格时的网格状态：如果 $P_{i,j,k}$ 是 #，则从上数第 $j$ 行、从左数第 $k$ 列的小格被该多联骨牌占据；如果是 .，则该小格未被占据。（参照样例输入/输出 1 的图。）

你想用这三个多联骨牌填满网格，使以下所有条件成立：

• 网格的所有小格都被多联骨牌覆盖。
• 多联骨牌之间互不重叠。
• 多联骨牌不能超出网格。
• 多联骨牌可以任意平移和旋转，但不能翻转。

能否用这些多联骨牌填满网格以满足上述条件？

输入格式

输入按以下格式从标准输入给出。第 $i$ 个多联骨牌由第 $4(i-1)+1$ 行到第 $4i$ 行表示：

$P_{1,1,1}P_{1,1,2}P_{1,1,3}P_{1,1,4}$
$P_{1,2,1}P_{1,2,2}P_{1,2,3}P_{1,2,4}$
$P_{1,3,1}P_{1,3,2}P_{1,3,3}P_{1,3,4}$
$P_{1,4,1}P_{1,4,2}P_{1,4,3}P_{1,4,4}$
$P_{2,1,1}P_{2,1,2}P_{2,1,3}P_{2,1,4}$
$P_{2,2,1}P_{2,2,2}P_{2,2,3}P_{2,2,4}$
$P_{2,3,1}P_{2,3,2}P_{2,3,3}P_{2,3,4}$
$P_{2,4,1}P_{2,4,2}P_{2,4,3}P_{2,4,4}$
$P_{3,1,1}P_{3,1,2}P_{3,1,3}P_{3,1,4}$
$P_{3,2,1}P_{3,2,2}P_{3,2,3}P_{3,2,4}$
$P_{3,3,1}P_{3,3,2}P_{3,3,3}P_{3,3,4}$
$P_{3,4,1}P_{3,4,2}P_{3,4,3}P_{3,4,4}$

输出格式

如果能够用多联骨牌填满网格并满足题目描述中的所有条件，输出 Yes；否则输出 No。

样例

....
###.
.#..
....
....
.###
.##.
....
..#.
.##.
.##.
.##.

Yes

下图展示了与样例输入 1 对应的多联骨牌形状。在这种情况下，按下图所示放置它们，可以填满网格并满足题目条件，因此答案为 Yes。

###.
#.#.
##..
....
....
..#.
....
....
####
##..
#...
#...

Yes

如样例输入 2 中的第一个多联骨牌所示，多联骨牌也可以是带孔的多边形形状。

##..
#..#
####
....
....
##..
.##.
....
.#..
.#..
.#..
.#..

No

注意，填满网格时多联骨牌不能翻转。

....
..#.
....
....
....
..#.
....
....
....
..#.
....
....

No

....
####
#...
#...
....
####
...#
..##
....
..##
..#.
..##

No

###.
.##.
..#.
.###
....
...#
..##
...#
....
#...
#...
#...

Yes

数据范围

• $P_{i,j,k}$ 是 # 或 .。
• 给定的多联骨牌是连通的。也就是说，组成一个多联骨牌的小格可以只通过上下左右相邻的小格互相到达。
• 给定的多联骨牌非空。