AT_abc007_3 [ABC007C] 幅優先探索

[problemUrl]: https://atcoder.jp/contests/abc007/tasks/abc007_3 たかはし君は迷路が好きです。今、上下左右に移動できる二次元盤面上の迷路を解こうとしています。盤面は以下のような形式で与えられます。 - まず、盤面のサイズと、迷路のスタート地点とゴール地点の座標が与えられる。 - 次に、それぞれのマスが通行可能な空きマス(`.`)か通行不可能な壁マス(`#`)かという情報を持った盤面が与えられる。盤面は壁マスで囲まれている。スタート地点とゴール地点は必ず空きマスであり、スタート地点からゴール地点へは、空きマスを辿って必ずたどり着ける。具体的には、入出力例を参考にすると良い。 今、彼は上記の迷路を解くのに必要な最小移動手数を求めたいと思っています。どうやって求めるかを調べていたところ、「幅優先探索」という手法が効率的であることを知りました。幅優先探索というのは以下の手法です。 - スタート地点から近い(たどり着くための最短手数が少ない)マスから順番に、たどり着く手数を以下のように確定していく。説明の例として図1の迷路を利用する。  図1. 説明に用いる盤面- 最初に、スタート地点は、スタート地点から手数0でたどり着ける(当然)ので、最短手数0で確定させる(図2)。  図2. 最短手数0でたどり着けるマスが確定(初期)- 次に、スタート地点の四近傍(上下左右)の空きマスについて、手数1で確定させる(図3)。  図3. 最短手数1でたどり着けるマスが確定- 次に、手数1で確定したそれぞれのマスの4近傍を見て、まだ確定していない空きマスがあればそのマスを手数2で確定させる(図4)。  図4. 最短手数2でたどり着けるマスが確定- 次に、手数2で確定したそれぞれのマスの4近傍を見て、まだ確定していない空きマスがあればそのマスを手数3で確定させる(図5)。  図5. 最短手数3でたどり着けるマスが確定- 次に、手数3で確定したそれぞれのマスの4近傍を見て、まだ確定していない空きマスがあればそのマスを手数4で確定させる(図6)。  図6. 最短手数4でたどり着けるマスが確定- 上記の手順を確定の更新が無くなるまで繰り返すと、スタート地点からたどり着ける全ての空きマスについて最短手数が確定する(図7)。スタートとゴールは必ず空きマスを辿ってたどり着けるという制約があるので、ゴール地点への最短手数も分かる。  図7. すべてのたどり着けるマスへの最短手数が確定さて、この処理をスマートに実装するためには、先入れ先出し(FIFO)のキュー(Queue)というデータ構造を用いると良いことが知られています。もちろん、使わなくても解くことは可能です。今回、よく分からなければ思いついた方法で解くことをおすすめします。先入れ先出しのキューとは以下のような機能を持つデータ構造です。 - 追加(Push): キューの末尾にデータを追加する。 - 取り出し(Pop): キューの先頭のデータを取り出す。 このデータ構造を使うと、先ほどの幅優先探索の説明における「マスの最短手数の確定」のタイミングでその確定マスをキューに追加し、追加操作が終わればPopを行い、取り出したマスの4近傍を調べるということを繰り返せば(つまり先に追加されたものから順番に処理していけば)、簡潔に処理ができることが分かります。

N/A

N/A

### Sample Explanation 1 問題文中の例です。 ### Sample Explanation 2 図8のように進めば $ 10 $ 手でたどり着くことが進むことができます(※Sはスタート、Gはゴールをあらわす)。 !\[\](http://abc007.contest.atcoder.jp/img/abc/007/3-1.png) 図8. 入出力例2において最小手数10を達成する進み方 ### Sample Explanation 3 もはやただの広い空間であり、迷路と呼んで良いのかは分からないがこの問題でこのような盤面も迷路として扱う。兎にも角にも、スタートからゴールへの最短手数は $ 94 $ である。