問題一覧 > 通常問題

No.424 立体迷路

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 288
作問者 : はむこ / テスター : btk
7 ProblemId : 1326 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-06-23 15:14:54

問題文

あなたはh×wの立体迷路に閉じ込められた。立体迷路の枠の外に出ることはできない。
始めは(sx,sy)にいる。ゴール(gx,gy)に到着すると、ワープで脱出できる。

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

脱出可能か。

入力

h w
sx sy gx gy
b1

bh

2h50
2w50
1sxh
1syw
1gxh
1gyw
biは'0'から'9'までを含む長さwの文字列。bij文字目は(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もしくは右上の雲マークをクリックしてアカウントを作成してください。