[AOJ] No. 0558 Cheese

Cheese

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0558

迷路を解く定番の問題です。キューを使った幅優先探索を行いました。

考え方

方針

この問題のねずみは工場を \( 1 \) から \( N \) まで順番に訪れます。ねすみの初期位置はSなので、まず初めにSから \( 1 \) までの最短経路の長さを計算します。つぎに、 \( 1 \) から \( 2 \) までの最短経路を求めます。この手順を \( N \) まで繰り返します。

幅優先探索を用いて迷路の解法

幅優先探索をつかった迷路の解き方は検索すれば沢山出てくると思いますが、自分の書き方は、マスを訪れたかどうかの状態を管理する二次元配列と調査中のマスを格納するキューを使っています。この問題では上下左右の4方向に移動ができるので、注目するマスの4方向が移動可能ならばキューに移動先のマスを格納していきます。

ソースコード

シェアする

  • このエントリーをはてなブックマークに追加

フォローする