← 返回题目列表

AtCoder · abc285_g

G. 榻榻米

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

分数: 600 点

问题陈述

我们有一个网格 H 水平行和 W 垂直列。 我们用平方表示 (i,j) 广场 i从顶部开始的第行和 j左起第 列。

我们想用以下内容覆盖这个网格 1 \times 1 瓷砖和 1 \times 2 平铺,以便没有平铺重叠并且到处都被平铺覆盖。 (图块可以旋转。)

每个方格都有 上面写着 1, 2,或 ? 。 方格上写着的字 (i, j) is c_{i,j}.
一个正方形 其上写的 1 必须被 1 \times 1 瓷砖,和一个正方形 2 由 1 \times 2 瓷砖。 一个正方形与 ? 可以被任何类型的瓷砖覆盖。

确定是否存在这样的瓷砖放置位置。

约束

  • 1 \leq H,W \leq 300
  • H 和 W 是整数。
  • c_{i,j} 是其中之一 1, 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 否则。


示例输入 1

3 4
2221
?1??
2?21

示例输出 1

Yes

例如,以下放置满足条件。


示例输入 2

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

示例输出 2

No

没有满足条件的展示位置。


示例输入 3

5 5
11111
11111
11211
11111
11111

示例输出 3

No