No.424 立体迷路

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 158
作問者 : はむこはむこ / テスター : btkbtk

3 ProblemId : 1326 / 出題時の順位表

問題文

あなたは$h \times w$の立体迷路に閉じ込められた。立体迷路の枠の外に出ることはできない。
始めは$(s_x, s_y)$にいる。ゴール$(g_x, g_y)$に到着すると、ワープで脱出できる。

はしごを使うことで、以下の前後左右の移動ができる(斜めには移動できない)。
(1) 隣り合った同じ高さのブロックに、歩いて移動する
(2) 隣り合った1つだけ高いブロックに、はしごを立てかけて登る
(3) 隣り合った1つだけ低いブロックに、はしごを立てかけて下る
(4) 同じ高さの2つ先のブロックに、はしごを渡して移動する。はしごを渡すためには、間にあるブロックが今いるブロックの高さより低い必要がある(サンプル3参照)。

脱出可能か。

入力

$h\ w$
$s_x\ s_y\ g_x\ g_y$
$b_1$
$\vdots$
$b_h$

$2 \leq h \leq 50$
$2 \leq w \leq 50$
$1 \leq s_x \leq h$
$1 \leq s_y \leq w$
$1 \leq g_x \leq h$
$1 \leq g_y \leq w$
$b_i$は'0'から'9'までを含む長さ$w$の文字列。$b_i$の$j$文字目は$(i, j)$のブロックの高さを表す。

出力

脱出可能ならばYES, 脱出不可能ならばNOを出力せよ。 最後に改行してください。

サンプル

サンプル1
入力
3 5
3 5 1 1
43000
12023
00014
出力
YES

はしごで4回降りて、4回登ればゴールできます。

サンプル2
入力
3 5
3 5 1 1
63000
12023
00014
出力
NO


サンプル3
入力
3 5
2 4 2 2
00000
09090
00000
出力
YES

はしごは横に使うこともできます(ルール4)。

サンプル4
入力
6 6
6 6 1 1
202020
020202
202020
020202
202020
020202
出力
NO

同じ高さでも、斜めには移動できません。

サンプル5
入力
10 12
4 1 1 12
879572576859
445569966665
033345689389
011246557476
000224557745
000022346548
000000425665
000002223544
000000003223
000000000243
出力
YES

最低2回はしごを横に使うことで到達できます。

提出ページヘ