$H$ 行 $W$ 列からなるグリッドがあります。以降、グリッド上の $i$ 行目 $j$ 列目のマスを $(i, j)$ のマスと書きます。
グリッドの各マスには、$1$ 以上 $6$ 以下の数字か、あるいは #
の文字が $1$ つずつ書かれています。ただし、$i$ と $j$ がともに偶数であるような $(i, j)$ のマスには必ず #
が書かれています。
あなたは以下の図で表されるようなサイコロを $1$ つ持っています。
最初、あなたはこのサイコロを底面が $6$, 前面が $2$, 右面が $3$ となるように $(1, 1)$ のマスに置きます。 ここで、前面は $(i, j)$ の $i$ が増える方向の面を、右面は $j$ が増える方向の面を指します。
その後、サイコロが置かれているマスに辺で隣接する $4$ マスのいずれかにサイコロを転がす操作を好きな回数繰り返すことができます。 サイコロを転がす際、サイコロは転がす方向に90度回転します。
ただし、サイコロを転がす際には以下の条件を満たしている必要があります。
#
が書かれているマスに転がしてはならない$(1, 1)$ のマスには必ず $6$ が書かれていることが保証されます。
サイコロを転がす操作を繰り返すことで、サイコロを $(1, 1)$ のマスから $(H, W)$ のマスに移動させることができるか判定してください。
#
が書かれている#
が書かれている入力は以下の形式で標準入力から与えられる。
$H$ $W$ $s_{11}s_{12} \ldots s_{1W}$ $s_{21}s_{22} \ldots s_{2W}$ $\vdots$ $s_{H1}s_{H2} \ldots s_{HW}$
ここで、$s_{ij}$ は $(i, j)$ のマスにかかれている数字または文字を表す。
すなわち、$s_{ij}$ は $1$ 以上 $6$ 以下の数字であるか、あるいは #
である。
$(1, 1)$ のマスから $(H, W)$ のマスへサイコロを転がして移動させることができるならば YES
を、そうでないならば NO
を 1 行で出力せよ。
3 3 631 4#2 516
YES
$(1, 1), (1, 2), (1, 3), (2, 3), (3, 3)$ の順に転がすことで、到達可能です。
3 3 6#1 ##2 516
NO
5 5 61244 2#5#3 14641 5#5#5 63126
YES