1. paizaラーニングトップ
  2. レベルアップ問題集
  3. グリッド版ダイクストラ問題セット(言語選択)
  4. 問題一覧 C#編
  5. 問題1: 幅優先探索 - 迷路 (hard)

グリッド版ダイクストラ問題セットのサムネイル
問題1: 幅優先探索 - 迷路 (hard) (paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう!

問題

下記の問題をプログラミングしてみよう!

この問題は前問 (問題1: 幅優先探索 - 迷路) の制約強化版です。

グリッド状の盤面で上下左右の移動を繰り返して、左上のスタートから右下のゴールまで移動するときに通るマス (スタート、ゴール含む) の最小の個数を求めてください。ただし、0 のマスは通れて、1 のマスは通れません。なお、0 のマスのみを通ってスタートからゴールまで移動できることが保証されています。

※この問題は、paiza開発日誌で詳しく解説しています

入力される値

h w
t_{0,0} t_{0,1} ... t_{0,w-1}
t_{1,0} t_{1,1} ... t_{1,w-1}
...
t_{h-1,0} t_{h-1,1} ... t_{h-1,w-1}


・ 1 行目には盤面の行数を表す h , 盤面の列数を表す w が与えられます。
・ 続く h 行のうち i 行目には、盤面 の i 行目を表す整数値のリスト t_i が与えられます。
・ t_{i,j} は i 行目の j 列目の値です。


入力値最終行の末尾に改行が1つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
期待する出力

左上のスタートから右下のゴールまで移動するときに通るマス (スタート、ゴール含む) の最小の個数を 1 行で出力してください。

条件

すべてのテストケースにおいて、以下の条件をみたします。

・ 1 ≦ h , w ≦ 500
・ 0 ≦ t_{i,j} ≦ 1 (0 ≦ i < h, 0 ≦ j < w)

入力例1

3 6
0 0 1 0 0 0
1 0 1 0 1 0
0 0 0 0 1 0

出力例1

12

問題一覧へ戻る

ページの先頭へ戻る