[AOJ] No. 0037 Path on a Grid

Path on a Grid

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

考え方

題意

壁に右手をつきながら迷路を進み、入り口に戻るまでの行動を出力します。

方針

所謂、迷路の右手法のようなアルゴリズムを実装すれば良いと思います。

まず初めに与えられる迷路の格子点の数は \( 25 \) 個あることが分かります。格子点1つ1つをノードとみて、全ての格子点に対して、隣接する格子点を対応させます。ある格子点は最大でも上下左右の \( 4 \) 方向なので、要素数が \( 4 \) の配列を各格子点に持たせます。

格子点の番号の振り方は、\( r \) 行 \( c \) 列の格子点の番号は \(5r + c \) とします。

ある格子点から別の格子点への行き方で方向のパターンは、現在向いている方向と、壁によって変わる方向を合わせて \( 16 \) 通りあります。

動き方は、今いる格子点から隣接している格子点にしか進むことができず、向いている方向によって進むべき格子点の優先順位があります。

例えば、右を向いているときは、壁を挟んで上側に人が居なければいけないので、優先順位は、上、右、下、左となります。このように全ての方向に対して優先順位を持たせることでこの問題を解くことができます。

また、優先順位の \( 2 \) 番目は必ず今向いている方向になり、優先順位の \( 4 \) 番目は反対方向になり、来た道を戻る行動に相当します。

コード

感想

こういう問題は得意ではありませんが、解けて良かったです。

シェアする

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

フォローする