CodeIQ：突進するイノシシ

問題の概要

私のプログラム

Rubyで解答しています。

#!/usr/bin/ruby

# 入力値からのマップ
# 周囲は全てXで埋める
$BaseMap = []

# 入力値の1行め
$N=0

# マップ
# 進行可能な方向をビットで表す。
# 	0b0000：X
# 	0b0001:上、0b0010:下、0b0100:右、0b1000:左
$Map = []

# ゴールに到達したパターン
$Goals = []

# $Mapを作る
def makeMap()
	for i in 0...$BaseMap.length
		$Map.push([])
		for j in 0...$BaseMap[i].length
			c = $BaseMap[i][j]
			if c == "X" then $Map[i].push(0)
			else
				v = 0
				if $BaseMap[i-1][j] == "O" then v |= 0b0001 end	# 上
				if $BaseMap[i+1][j] == "O" then v |= 0b0010 end	# 下
				if $BaseMap[i][j-1] == "O" then v |= 0b0100 end	# 左
				if $BaseMap[i][j+1] == "O" then v |= 0b1000 end	# 右

				$Map[i].push(v)
			end
		end
	end
end

class Pos
	def initialize(y=-1, x=-1, d=0, path=nil, turn=0)
		@x = x		# X座標
		@y = y		# Y座標
		@d = d		# 次の進行方向
		@turn = turn	# 方向転換回数

		if path == nil then @path = [100*y+10*x+d]
		else @path = path.dup.push(100*y+10*x+d)
		end
	end

	# 異動先のPosオブジェクトのリストを返す。
	# @param gl ゴール座標
	# @return 異動先のPosオブジェクトのリスト
	def getNexts(gl)
		nxts = []

		# 次の位置に進む
		ny = -1; nx = -1
		if @d == 0b0001 then ny = @y-1; nx = @x end
		if @d == 0b0010 then ny = @y+1; nx = @x end
		if @d == 0b0100 then ny = @y; nx = @x-1 end
		if @d == 0b1000 then ny = @y; nx = @x+1 end

		# 次の場所で進行可能な方向
		nd = $Map[ny][nx]
#		puts "(ny, nx)=" + [ny,nx].to_s + ", nd=" + nd.to_s + ", @d=" + @d.to_s	#DEBUG

		# ゴールに達した場合
		if [ny, nx] == gl then
			nxts.push(self.moveNewPos(ny, nx, 0))
#			p "Goal!!"	#DEBUG
		# 次に同じ方向に進める場合
		elsif (@d &apm; nd) != 0 then
			nxts.push(self.moveNewPos(ny, nx, @d))
#			p "Go Straight"	#DEBUG
		else
			# 現在上下方向に移動
			if (@d & 0b0011) != 0 then
				# 次は左右のどちらかに移動する
				if (nd & 0b0100) != 0 then nxts.push(getNewPos(ny, nx, 0b0100, 1)) end
				if (nd & 0b1000) != 0 then nxts.push(getNewPos(ny, nx, 0b1000, 1)) end
#				p "Turn LR"	#DEBUG

			# 現在左右に移動
			elsif (@d & 0b1100) != 0 then
				# 次は上下のどちらかに移動する
				if (nd & 0b0001) != 0 then nxts.push(getNewPos(ny, nx, 0b0001, 1)) end
				if (nd & 0b0010) != 0 then nxts.push(getNewPos(ny, nx, 0b0010, 1)) end
#				p "Turn UD"	#DEBUG
			end
		end
#		p nxts	#DUBUG
		return nxts.compact
	end

	# 現在ゴールにいる場合はtrue、そうでない場合はfalseを返す
	def isGoal(gl)
		if @y == gl[0] && @x == gl[1] then return true
		else return false
		end
	end

	# 次の場所を新規に作成する
	# 方向転換が発生した時は2以上の方向に進める可能性があるのでこのメソッドで新たにオブジェクト
	# を作る
	# @param ny 次のy座標
	# @param nx 次のx座標
	# @param nd 次の方向
	# @param turn 方向転換回数に加える数（1か0）
	# @return 次のPosオブジェクト。同じ場所の繰り返しを検出した場合はnil。
	def getNewPos(ny, nx, nd, turn)
		if @path.include?(100*ny+10*nx+nd) then return nil
		else return Pos.new(ny, nx, nd, @path, @turn + turn)
		end
	end

	# 現在の位置から次の位置に移動する
	# 直進の場合、2つ以上の進行方向の候補ができることはないのでこのメソッドでオブジェクトを更新
	# する
	# @param ny 次のy座標
	# @param nx 次のx座標
	# @param nd 次の方向
	# @return レシーバ自身
	def moveNewPos(ny, nx, nd)
		self.y = ny
		self.x = nx
		self.d = nd
		self.path.push(100*ny+10*nx+nd)
		return self
	end

	attr_accessor :x, :y, :d, :path, :turn
end

# イノシシに探索させる
# @param st スタート座標
# @param gl ゴール座標
def goBoar(st, gl)
	queue = []	# 探索用キュー

	# 初期状態を作る
	# 初期状態ではそのマスから進行可能な方向を全てスタックに積む
	for d in [0b0001, 0b0010, 0b0100, 0b1000]
		nd = $Map[st[0]][st[1]]
		if (nd & d) != 0 then
			queue.push(Pos.new(st[0], st[1], nd & d))
		end
	end

	nqueue = []	# キュー更新用
	goal = nil	# ゴールに達したもの
	while !queue.empty?

		now = queue.shift
		# ゴールに到達している場合
		if now.isGoal(gl) then
			if goal == nil then
				goal = now
			elsif goal.turn > now.turn then
				goal = now
			end
		end

		# 次の場所に移動する
		nqueue += now.getNexts(gl)

		# まだ現在の距離の探索がキューに残っている間はそれを続ける
		if queue.empty? then
			# ゴールに達したものがない場合はキューを更新
			if goal == nil then
				queue = nqueue
				nqueue = []
			else
				$Goals.push(goal)
				break
			end
		end
	end
end

# ターン数の最大値を求める
def getMaxTurn()
	mx = 0
	if $Goals.empty? then return 0 end

	for g in $Goals
		if g.turn > mx then
			mx = g.turn
#			p g	#DEBUG
		end
	end

	return mx;
end

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

	if ln == 0 then
		$N = line.to_i
		$BaseMap.push("X"*($N+2))
	else
		$BaseMap.push("X" + line + "X")
	end
	ln += 1
end
$BaseMap.push("X"*($N+2))

makeMap()

# 全てのスタート地点、ゴール地点についてテストする
for sy in 1..$N
	for sx in 1..$N
		for gy in 1..$N
			for gx in 1..$N
				if $BaseMap[sy][sx] == "X" then next end
				if (sx == gx) && (sy == gy) then next end
				goBoar([sy,sx],[gy,gx])
			end
		end
	end
end

p getMaxTurn()

解説

この問題は出題内容に曖昧な部分があります。実際のテストケースの中に「ある点の組み合わせで同じマス数（最短距離）だがターン数が3の場合と4の場合が存在する」のですが、この時に答えとしては3を選択しなければなりません。
問題の最短距離がターン数だとすると「ある点の組み合わせでマス数は多いけれどターン数はより少なくなる」場合がありそうです（これは確認していません）。
この回答は結果に合わせる形で「ある一組のスタート地点とゴール地点の組み合わせで同じマス数（距離）で異なるターン数の結果が得られた場合、ターン数の少ない方を最短距離とする」としています。

雑感

★★★の問題で相応に難しいと思いますが、「激ムズ！頭脳を【上限解放】～電脳体キュラゲタムを討伐せよ」と似た問題だったのでそれほど悩まずにできました（それでも1回時間切れ、1回は問題の曖昧さのためリジェクトされましたが）。