AT_abc285_g [ABC285G] 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。

输入输出样例 #1

输入 #1

3 4
2221
?1??
2?21

输出 #1

Yes

输入输出样例 #2

输入 #2

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

输出 #2

No

输入输出样例 #3

输入 #3

5 5
11111
11111
11211
11111
11111

输出 #3

No

说明/提示

限制条件

• $1 \leq H, W \leq 300$
• $H, W$ 为整数
• $c_{i,j}$ 为 1、2 或 ?

样例解释 1

例如如下图所示的瓷砖铺放方式可以满足条件。

样例解释 2

不存在满足条件的瓷砖铺放方式。

由 ChatGPT 4.1 翻译