AT_abc322_d [ABC322D] Polyomino

题目描述

将若干个正方形通过边相连形成的连通多边形形状的拼图块称为 多连方块（ポリオミノ）。

现在有一个 $4$ 行 $4$ 列的网格，以及 $3$ 个可以放入该网格的多连方块。
第 $i$ 个多连方块的形状由 $16$ 个字符 $P_{i,j,k}$（$1 \leq j, k \leq 4$）表示。$P_{i,j,k}$ 表示将第 $i$ 个多连方块放在一个空网格上的状态，若 $P_{i,j,k}$ 为 #，则表示该多连方块覆盖了从上到下第 $j$ 行、从左到右第 $k$ 列的格子；若为 .，则表示未覆盖。请参考输入输出样例 $1$ 的图示。

你需要将这 $3$ 个多连方块全部铺在网格上，并满足以下所有条件：

• 网格的所有格子都被多连方块覆盖。
• 多连方块之间不能重叠。
• 多连方块不能超出网格边界。
• 多连方块可以任意平移和旋转，但不能翻转。

请判断是否存在一种方式，使得可以将这 $3$ 个多连方块铺满整个网格，并满足上述条件。

输入格式

输入通过标准输入给出，格式如下：

$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

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

输出 #1

Yes

输入输出样例 #2

输入 #2

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

输出 #2

Yes

输入输出样例 #3

输入 #3

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

输出 #3

No

输入输出样例 #4

输入 #4

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

输出 #4

No

输入输出样例 #5

输入 #5

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

输出 #5

No

输入输出样例 #6

输入 #6

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

输出 #6

Yes

说明/提示

限制条件

• $P_{i,j,k}$ 只会是 # 或 .。
• 给定的多连方块都是连通的。即，多连方块由正方形组成，这些正方形之间可以通过上下左右方向互相到达。
• 给定的多连方块不会是空的。

样例解释 1

与输入样例 $1$ 对应的多连方块形状如下图所示。

在这种情况下，可以如下图所示地放置多连方块，使其满足题目要求。

因此答案为 Yes。

样例解释 2

在输入样例 $2$ 中，第 $1$ 个多连方块的形状可能是带有空洞的多边形。

样例解释 3

请注意，铺放多连方块时，不能将其翻转。

由 ChatGPT 4.1 翻译