No.424 立体迷路
問題文最終更新日: 2018-06-23 15:14:54
問題文
あなたは$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回はしごを横に使うことで到達できます。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。