102856: [AtCoder]ABC285 G - Tatami

Problem Statement

We have a grid with $H$ horizontal rows and $W$ vertical columns. We denote by square $(i,j)$ the square at the $i$-th row from the top and $j$-th column from the left.

We want to cover this grid with $1 \times 1$ tiles and $1 \times 2$ tiles so that no tiles overlap and everywhere is covered by a tile. (A tile can be rotated.)

Each square has 1, 2, or ? written on it. The character written on square $(i, j)$ is $c_{i,j}$.
A square with 1 written on it must be covered by a $1 \times 1$ tile, and a square with 2 by a $1 \times 2$ tile. A square with ? may be covered by any kind of tile.

Determine if there is such a placement of tiles.

Constraints

• $1 \leq H,W \leq 300$
• $H$ and $W$ are integers.
• $c_{i,j}$ is one of 1, 2, and ?.

Input

The input is given from Standard Input in the following format:

$H$ $W$
$c_{1,1}c_{1,2}\ldots c_{1,W}$
$\vdots$
$c_{H,1}c_{H,2}\ldots c_{H,W}$

Output

Print Yes if there is a placement of tiles to satisfy the conditions in the Problem Statement; print No otherwise.

Sample Input 1

3 4
2221
?1??
2?21

Sample Output 1

Yes

For example, the following placement satisfies the conditions.

Sample Input 2

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

Sample Output 2

No

There is no placement that satisfies the conditions.

Sample Input 3

5 5
11111
11111
11211
11111
11111

Sample Output 3

No

问题描述

我们有一个由 $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$ 的瓷砖覆盖。写有 ? 的正方形可以用任何类型的瓷砖覆盖。

判断是否存在这样的瓷砖放置方式。

约束条件

• $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