さて勝手に始めている競技プログラミングシリーズの出題編第3問
前回の「宝の地図集め」では人により様々な実装があったと思うが今回の「最短経路探索」では多くの人が同様の方針を立てると思う
第3問 「最短経路探索」 Lv. ★★★
————————————————————
入力として壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を出力するプログラムを作成してください。
具体的には S:スタート G:ゴール *:壁 $:解答の経路 としたとき、
************************** *S* * * * * * * ************* * * * * ************ * * * * ************** *********** * * ** *********************** * * G * * * *********** * * * * ******* * * * * * **************************
という入力に対し、
************************** *S* * $$$ * *$* *$$*$ ************* * *$* $$* $$$************ * *$$$$* $$$$$ * **************$*********** * $$$$$$$$$$$$$ * **$*********************** * $$$$$*$$$$$$$$$$$$$$G * * * $$$ *********** * * * * ******* * * * * * **************************
という出力をするプログラムを作成してください。
解答にあたっては、以下に留意してください。
● 一度に動けるのは上下左右のみ。斜めは不可
● 最短経路が複数あるときはそのうちの１つが出力されていればよい
● 入力データのバリデーション（長方形になっているか、スタート・ゴールが１つずつあるかどうか、等）は不要
● 迷路の幅・高さの最大値は30
※ 入力には標準入力、出力には標準出力を用いてください。
————————————————————
問題は全部で4問なので出題編は次回で一旦終了ということになる
今回の問題は如何にもアルゴリズムテストのために設えられたようなもので殆どの人はグラフ理論の木構造を用いることになるだろう
その上で深さ優先なのか幅優先なのかという走査法の選択と処理速度の改善のため無駄な探索をどれだけ省略出来るかが問われている
