/ 
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
縦 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
Score : 600 points
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