CodeIQ：【実力判定：Sランク】まっすぐ行こう

私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「【実力判定：Sランク】まっすぐ行こう」（CodeIQ）を参照してください。

問題の概要

問題を引用します。
【問題】
M×Nのマス目を左上から右下に向かって移動します。移動方向は上下左右のみです。
ただし、マス目上には通れない箇所がいくつかあります。同じ点を2回以上通過しても構いません。
fig.1

上図の黄色い部分をスタート、青い部分をゴールとし、黒い部分は通れないものとします。
このとき、スタートからゴールまでの経路はいくつか考えられますが、できるだけ方向転換の回数が少ない経路を見つけてください。

fig.2

左図の経路では方向転換（★印の部分が）2か所ですが、右図では方向転換が1か所だけですので、このケースでは1回の方向転換でゴールまで到達できることになります。

【入力】
標準入力から、1行目に半角スペースで区切られた2つの整数値M, N（1≦M, N≦64）が与えられます。
2行目から（M+1)行目までは長さNの文字列です。文字列は、' .'と'#'で構成されています。
'.'は移動できる部分、'#'は移動できない部分を表します。
2行目の1文字目と、（M+1）行目のN文字目、つまりスタート地点とゴール地点に相当する点は必ず'.'になっています。
また、スタートからゴールに到達する経路が必ず存在するものとします。

【出力】
マス目の左上から右下まで移動する経路の中で、方向転換する回数の最小値を、標準出力に出力してください。

【入出力サンプル】
Input
2 3
..#
...
標準出力
1

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

$Map = []

class Pos
	attr_reader :now, :dir
	attr_accessor :turn

	def initialize(n = [0,0], d = [0,0])
		@now = n
		@dir = d
		@turn = -1
	end

	def next(to)
		nr = @now[0] + to[0]
		nc = @now[1] + to[1]

		# 範囲外
		if (nr < 0) || (nc < 0) || (nr >= M) || (nc >= N) then
			return nil
		end

		# 侵入不能な場所
		if $Map[nr][nc] == "#" then
			return nil
		end

		nxt = Pos.new([nr, nc], to)
		if @dir != nxt.dir then
			nxt.turn = @turn + 1
		else
			nxt.turn = @turn
		end

		return nxt
	end
end

def solve()
	direction = [[-1,0], [1,0], [0,-1], [0,1]]	# 上下左右
	memo = Array.new(M){Array.new(N, 65535)}
	memo[0][0] = 0

	queue = [Pos.new()]
	while !queue.empty?
		queue.sort!{|a,b| a.turn<=>b.turn}
		now = queue.shift
		for d in direction
			# 次の位置に進む
			nxt = now.next(d)

			# 範囲外なら無視
			if nxt == nil then next end

			# 次の位置に進んだときのターン数以下なら更新してキューに追加
			# 同じ場所を2個以上保持することになるが、直進してくる可能性がある
			if nxt.turn <= memo[nxt.now[0]][nxt.now[1]] then
				memo[nxt.now[0]][nxt.now[1]] = nxt.turn
				queue << nxt
			end
		end
	end

	return memo[M-1][N-1]
end

# main
ln = 0
while line = gets
	line.strip!
	if line.empty? then next end

	if ln == 0 then
		M,N = line.split.map{|a| a.to_i}
	elsif ln > 0 then
		$Map << line.split("")
	end

	ln += 1
end

p solve()

解説

Sランクの問題です。
Aランクの問題と難易度はあまり変わらないのではないでしょうか。

考え方

基本的に最短経路探索の問題なので幅優先探索を応用すればできます。
ポイントは方向転換の回数がコストになる点です。方向転換した先が行き止まりでなければ任意の場所で方向転換できるため、通過した途中地点のコストが同じでもその先で直進できるパターンがあるということが起こりえます。

次の様な入力を考えてください。
....
...#
#...
パターンA パターンB
↓...
1→2#
#.3→
→1..
.↓.#
#2→→

他にもパターンはありますが説明にはこれで十分です。
もっとも基本的な幅優先探索では各地点に到達するための最小コストを記録し、ある地点に到達したコストがより少ない場合は記録を更新し、コストが同じかそれ以上のものは切り捨てます。これが問題になります。
例えば上下左右の順で探索する場合、シアンの矢印の場所を探索するのはパターンAがパターンBよりも先にります。この時のコストはともに1ですが、結果としてはパターンBの方が1回少ない方向転換でゴールします。
このことを考慮しておかないと正しい結果を求めることができません。

Posクラス

現在の位置(now)と進んできた向き(dir)、これまでの方向転換回数(turn)を保持するクラスです。

Pos#initialize()

コンストラクタは与えられた座標（n）と向き(d)をセットします。省略時はスタート地点になります。スタート地点ではどちらも向いていないので方向は[0,0]にします。
また、スタート地点でセットされた時に最初の移動が必ず方向転換になってしまうのでturnを-1で開始し、最初の移動で必ず1加算されて0になる様にします。

Pos#next()

引数に与えられた方向に進め、新しいオブジェクトを返します。
nrは引数toの方向に進んだ場合の行番号、ncは列番号で、現在の座標にtoの値を加えたものになります。
20〜22行目で範囲外をチェックし、25〜27行目で侵入できない場所をチェックします。侵入できない場所に進んだときはnilを返します。
進むこうとができる場所なら、その座標で新しいオブジェクトを生成します（29行目）。同時に前回と異なる方向ならturnを1増やし、同じなら同じ方向転換数にします。

solve()

幅優先探索（ダイクストラ法）で探索します。
directionは移動できる方向（上下左右）のベクトルです。
memoはある地点に到達した最小コストを記録する領域で、非常に大きな値で初期化しておきます（今回は65535）。43行目でスタート地点のコストを0にしていますが別に必要ありません（気分的に0にしておきたかった）。
queueは探索候補のPosオブジェクトのリストです。最初はスタート地点にいるのでスタート地点のオブジェクトだけをセットします。

探索はqueueが空になるまで行います（46〜61行目）。
まず、queueから最初の要素を取り出します（47行目）。
その値に対して上下左右に進めます（48〜60行目）。
現在位置(now)から進んだ場合（50行目）にnilが返ったらその場所は範囲外か"#"なので無視します（53行目）。
そうでなければmemoをチェックし、現在のコスト以下なら（58行目）memoの値を更新し（59行目）、queueにその地点の情報を追加します。「現在のコスト未満」ではなく「現在のコスト以下」であることがポイントです。これによって同じ地点で同じコストあっても方向が違えばqueueに残るので、「考え方」で考慮すべきとした部分をフォローできます。

最終的にゴール地点の値が答えになります（65行目）。

雑感

★★★★の問題ですが、それほど難しくはありません。多分、「突進するイノシシ」と同じくらいの難易度です（問題も似ています）。私は注意点として書いた部分で引っかかって1回再提出でした。ランクAまではミスなしでできたので4つの中では一番難しいのでしょう。
ちなみに、問題文の「同じ点を2回以上通過しても構いません。」が気になって仕方ありませんでした（一旦通過して反転した方が早い場合はないと思うのですが、この文章のためそういうことがあるのかと）。実際は関係ありませんでしたが。