Tatami

题目描述

我们有一个有 $H$ 行水平方向行和 $W$ 列垂直方向列的网格。我们用方格 $(i,j)$ 表示从上数第 $i$ 行、从左数第 $j$ 列的方格。 我们想用 $1 \times 1$ 瓦片和 $1 \times 2$ 瓦片覆盖此网格，使得瓦片之间不重叠且所有位置都被覆盖。（瓦片可以旋转。） 每个方格上写有 $1$、$2$ 或 $?$。方格 $(i, j)$ 上写的字符记为 $c_{i,j}$。
写有 $1$ 的方格必须被一个 $1 \times 1$ 瓦片覆盖，写有 $2$ 的方格必须被一个 $1 \times 2$ 瓦片覆盖。写有 $?$ 的方格可以被任意类型的瓦片覆盖。 判断是否存在这样的瓦片放置方案。

输入格式

输入从标准输入按以下格式给出： $H$ $W$ $c_{1,1}c_{1,2}\ldots c_{1,W}$ $\vdots$ $c_{H,1}c_{H,2}\ldots c_{H,W}$

输出格式

如果存在满足题目条件的瓦片放置方案，打印 $Yes$；否则打印 $No$。

3 4
2221
?1??
2?21

Yes

3 4
2?21
??1?
2?21

No

5 5
11111
11111
11211
11111
11111

No

提示

$1 \leq H,W \leq 300$ $H$ 和 $W$ 是整数。 $c_{i,j}$ 是 $1$、$2$ 和 $?$ 中的一个。例如，下面的放置满足条件。
不存在满足条件的放置。

标签: AtCoder|abc285G

来源

AtCoder|abc285G