AOJ 0037 (Path on a Grid : 格子上の経路)
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0037
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0037
【解説】
原点に戻ってくるまで、順番にルートを辿っていく。右手を壁に着け、壁伝いに進むため、以下のルールに従って進んでいけばよい。
- 進行方向に対して左手にルートがあれば、左手に進む。
- 進行方向にルートがあれば、進行方向に進む。
- 進行方向に対して右手にルートがあれば、右手に進む。
- いずれもなければ逆側に進む。
上記については、各交点ごとに壁の伸びている方向を東方向を0°として、反時計周りに正となるよう(ちょうどxy平面のように)に格納しておき、進行方向に対して、-90°、0°、90°、180°のルートがあるかを順にみていけばよい。
【コード】