Tiling

题目描述

有一个由 $H$ 行 $W$ 列组成的网格，每个单元格的边长为 $1$，并且我们有 $N$ 块瓦片。
第 $i$ 块瓦片（$1\leq i\leq N$）是一个大小为 $A_i\times B_i$ 的矩形。
判断是否有可能将瓦片放置在网格上，使得下列所有条件都被满足：

每个单元格恰好被一块瓦片覆盖。 未使用的瓦片是允许的。 瓦片放置时可以旋转或翻转。但每块瓦片必须与单元格的边对齐，且不得超出网格。

输入格式

输入从标准输入按以下格式给出： $N$ $H$ $W$ $A_1$ $B_1$ $A_2$ $B_2$ $\ldots$ $A_N$ $B_N$

输出格式

如果可以放置瓦片使得满足题目陈述中的所有条件，输出 $Yes$；否则输出 $No$。

5 5 5
1 1
3 3
4 4
2 3
2 5

Yes

1 1 2
2 3

No

1 2 2
1 1

No

5 3 3
1 1
2 2
2 2
2 2
2 2

No

提示

$1\leq N\leq 7$ $1 \leq H,W \leq 10$ $1\leq A_i,B_i\leq 10$ 所有输入值均为整数。如下面所示放置第 $2$、$4$、$5$ 块瓦片可以使网格的每个单元格恰好被一块瓦片覆盖。 因此，输出 $Yes$。
该瓦片不可能在不超出网格的情况下放置。
因此，输出 $No$。
无法用该瓦片覆盖所有单元格。
因此，输出 $No$。
注意每个单元格必须恰好被一块瓦片覆盖。

标签: AtCoder|abc345D

来源

AtCoder|abc345D