プログラム解説：CodeIQ「迷路」

問題の概要

問題を引用します。

【概要】
右図のような迷路があります。
一歩で、上下左右に進めますが、太線は壁なので超えられません。
右図の a, b, c, d は、門を表しています。
門は開いているかもしれませんし、閉じているかもしれません。
開いている門・スタート地点・ゴールを指定します。
スタートからゴールに行くには最低何歩必要なのかを計算してください。
※入力で指定された門以外は、全て閉じているものとします

【入力】
入力は三文字で、
a8K
のようになっています。

開いている門・スタート・ゴールの3つが区切り文字なしで並んでいます。

【出力】
スタート地点からゴール地点まで何歩なのかを10進数で出力してください。
先ほどの入力の場合、a が通行可能であれば 8 から K まで 4歩で行けるので、
4
を出力すれば正解です。

【例】

入力出力状況

a8K 4

b9L 4

cAS 3

dR3 8

【補足】
不正な入力に対処する必要はありません。

入力	出力	状況
a8K	4
b9L	4
cAS	3
dR3	8

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

$Map = [
	#0123456789abc
	"*************", #0
	"*0*1 2 3 4 5*", #1
	"* *** *** ***", #2
	"*6 7 8*9 AdB*", #3
	"***a*** * * *", #4
	"*C D*EbF*G*H*", #5
	"*** * ***c* *", #6
	"*I J K L*M N*", #7
	"* * ***** * *", #8
	"*O*P*Q R S*T*", #9
	"* *** ***** *", #10
	"*U V W*X Y Z*", #11
	"*************", #12
]

Gates = {
	"a" => [4, 3],
	"b" => [5, 6],
	"c" => [6, 9],
	"d" => [3, 10],
}

def openGate(x)
	Gates.each{|k, v|
		if k == x then $Map[v[0]][v[1]] = " "
		else $Map[v[0]][v[1]] = "*"
		end
	}
end

def position(v)
	for r in 0..12
		for c in 0..12
			return [r, c] if $Map[r][c] == v
		end
	end
end

def solve(gt, st, ed)
	openGate(gt)

	memo = Array.new(13){Array.new(13, 0xFFFF)}

	dir =[[-1,0], [0,1], [1,0], [0,-1]]
	ps = position(st)
	queue = [ps]

	memo[ps[0]][ps[1]] = 0

	while !queue.empty?
		now = queue.shift
		pt = memo[now[0]][now[1]] + 1

		for d in dir
			nr = now[0] + d[0]
			nc = now[1] + d[1]

			next if $Map[nr][nc] == "*"
			next if memo[nr][nc] < pt

			memo[nr][nc] = pt
			if $Map[nr][nc] == ed then
				return memo[nr][nc] / 2
			else
				queue << [nr,nc]
			end
		end
	end
end

# main
while line = gets
	line.strip!
	next if line.empty?
	gt, st, ed = line.split("")
	p solve(gt, st, ed)
end

解説

普通の最短経路探索の問題です。

考え方

最初に書いた通り、普通の最短経路探索の問題です。
考える必要があるのはマップをどう表現するかです。移動できるかできないかは壁の有無なので、0〜9とA〜Zの文字の分だけのマップだとうまく扱えません。やり方は色々あると思いますが私は単純に壁の場所もマップの要素として移動できない場所を'*'、移動できる場所を' 'で表現しました。

main

入力値を分割してsolve()に渡し、結果を印字します。
$Mapは迷路の地図で壁を'*'、通路を' 'にしています。ついでなので範囲外チェックを省くため外周は'*'で埋めました。
Gatesは（大したことはありませんが）$Mapを嘗めて門を探すのが嫌だったので座標を保持しているだけです。

solve()

幅優先探索です。

まず、openGate()で開いている門を' '、それ以外の門を'*'に置換します。これで以降は門のことを考えなくてよくなります。

memoは各座標に最小何歩で到達できたかを記録する領域です。
dirは侵攻方向（上、右、下、左）です。
psはスタート地点で、position()は引数の文字から座標を探す関数です。
queueは到達地点のqueueです。

後はqueueから要素を順次取り出し、dirの各方向に進めた場合にmemoの値未満で到達できたらmemoの値を更新してqueueに追加し、そうでなければ無視するという普通の幅優先探索です。
ゴール地点に到達したらその時のmemoの値の1/2を返却します（壁もマップ上の要素として表現しているので半分が答えになります）。

openGate(x)

$Mapのxの文字の場所を' '、それ以外の小文字英数字の場所を'*'にします。

position(v)

vの文字の場所の座標を返します。
スタート地点の座標を求めるためだけに使用します。

雑感

壁の表現さえうまくできれば難しくありません。
座標ごとに上下左右に進めるかを持たせるような方法もありますが、私がやったように壁の場所もマップの要素にしてしまうのが簡単と思います。

CodeIQ：迷路