← 返回题目列表

AtCoder · abc322_d

G. 多联骨牌

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

A 多联骨牌 是一个连接多边形形状的拼图,由多个正方形的边缘连接而成。

有一个四行四列的网格,以及三个适合该网格的多骨牌。
的形状 i-th 多联骨牌表示为 16 字符 P_{i,j,k} (1 \leq j, k \leq 4)。它们描述了当 i-th 多联骨牌被放置在其上。如果 P_{i, j, k} is #,位于 j从顶部开始的第行和 k左起第 列被多联骨牌占据;如果是的话 .,该方块未被占用。 (请参阅示例输入/输出中的图 1.)

您想要用所有三个多骨牌填充网格,以便满足以下所有条件。

  • 网格的所有方格都被多骨牌覆盖。
  • 多骨牌不得相互重叠。
  • 多骨牌不得伸出网格。
  • 多骨牌可以自由平移和旋转,但不能翻转。

网格中可以填充多骨牌来满足这些条件吗?

约束

  • P_{i, j, k} is # or ..
  • 给定的多联骨牌已连接。换句话说,组成多联骨牌的方格可以通过仅沿着上、下、左、右的方格相互到达。
  • 给定的多联骨牌不为空。

输入

输入由标准输入按以下格式给出:

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.


示例输入 1

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

示例输出 1

Yes

下图显示了 Sample Input 对应的多联骨牌的形状 1.

image1

在这种情况下,您可以通过如下图所示放置它们来填充网格以满足问题陈述中的条件。

image2

因此,答案是 Yes.


示例输入 2

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

示例输出 2

Yes

如样本输入中的第一个多联骨牌 2,多骨骨牌可以是带孔的多边形形状。


示例输入 3

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

示例输出 3

No

请注意,填充网格时多骨牌可能不会翻转。


示例输入 4

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

示例输出 4

No

示例输入 5

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

示例输出 5

No

示例输入 6

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

示例输出 6

Yes