CodeIQ：くねくね最短経路

問題の概要

私のプログラム

Pythonで解答しています。

#!/usr/local/bin/python3
# -*- coding:utf-8 -*-

import fileinput

class Maze:
	def __init__(self):
		self.Map = [[0 for j in range(8)] for i in range(8)]	# 探索対象の地図
		self.Memo = [[-1 for j in range(8)] for i in range(8)]	# 訪問履歴（-1は未訪問）
		self.Start = [0,0]	# スタート地点座標
		self.Goal = [8,8]	# ゴール地点座標
		self.Direction = ((-1,0),(1,0),(0,-1),(0,1))	# 上下左右
		self.Queue = []	# 進行方向候補 1要素の構成：[[座標X,Y],(Directionのどれか),反転回数]

	# 入力値から地図を作成する
	# 地図は一回り大きく作成し、外周は全て到達不能として扱う
	def createMap(self, input):
		i=1
		j=1
		for c in input:
			if (c == 's') or (c == 'g') or (c == '_'):
				self.Map[i][j] = 1

				if c == 's':
					self.Start = [i,j]
				elif c == "g":
					self.Goal = [i,j]

				j+=1

			elif c == 'X':
				self.Map[i][j] = 0
				j+=1
			elif c == '/':
				i += 1
				j=1

	def printMap(self):
		print("----- Map -----")
		for row in self.Map:
			print(row)
		print("Start:" + str(self.Start))
		print("Goal :" + str(self.Goal))

	def printMemo(self):
		print("----- Memo -----")
		for row in self.Memo:
			print(list(map(lambda a:str.format("{0:2d}",a),row)))

	# 進行方向と反対向きを返す
	def reverseDirection(self, d):
		if d == (1,0):
			return (-1,0)
		elif d == (-1,0):
			return (1,0)
		elif d == (0,1):
			return (0,-1)
		elif d == (0,-1):
			return (0,1)
		return (0,0)

	# 「くねくね最短経路」（https://codeiq.jp/q/2428）の探索
	def searchBend(self):
		# キューにスタート地点を入れる
		self.Queue.append([self.Start, (0,0), 0])

		# スタート地点の訪問履歴をセット
		self.Memo[self.Start[0]][self.Start[1]] = 0

		# 次のサイクルの探索候補
		nextQueue = []

		# キューが空になるかゴールに達するまで探索する
		while len(self.Queue) != 0:
			cur, bd, revC = self.Queue.pop(0)	# 現在の座標と前回の進行方向、反転回数
			if cur == self.Goal:
				return True

			# 反転は2回まで
			if revC <= 2:
				for d in self.Direction:	# 上下左右にわかれているので4回ループ
					#方向チェック（やってきた方向と同じ進行方向は処理しない）
					if d == bd:
						continue

					# 探索対象の座標
					x = cur[0] + d[0]
					y = cur[1] + d[1]

					# 座標が移動できないなら無視
					if self.Map[x][y] == 0:
						continue

					# 訪問先に到達するための歩数
					step = self.Memo[cur[0]][cur[1]] + 1

					# 座標が最短到達候補ならキューに追加して、Memoを更新
					if (d != self.reverseDirection(bd)) and (self.Memo[x][y] == -1):	# 進む場合は未訪問の場所だけ
						nextQueue.append([[x,y], d, 0])
						self.Memo[x][y] = step
					else:	# 戻る方向
						nextQueue.append([[x,y], d, revC+1])
						self.Memo[x][y] = step

			# 続きがある場合、Queueを再設定
			if (len(nextQueue) != 0) and (len(self.Queue) == 0) :
				self.Queue = nextQueue
				nextQueue = []

		return False

	def getStep(self):
		return self.Memo[self.Goal[0]][self.Goal[1]]

if __name__ == "__main__":
	for line in fileinput.input():
		if not line.strip():
			continue

		line = line.strip()

		maze = Maze()
		maze.createMap(line)
#		maze.printMap()
		ret = maze.searchBend()
#		maze.printMemo()
		if(ret):
			print(str(maze.getStep()))
		else:
			print("X")

解説

幅優先探索をひねった問題です。
わざわざクラスを作っていますが、別にクラスを作らなくてもできます。確か、Pythonを勉強中でクラスを使ってみたかったからクラスにしたのだと思います。
やたらと丁寧にコメントが入っているのであまり説明の必要はない気がしますが解説します。 Queueとメモ、ループを使った典型的な幅優先探索のロジックを元に実装しています。

雑感

この問題は見た瞬間に深さ優先探索でいけると思いましたが、最初、戻って良いことを考慮できておらず一度リジェクトされました。時間切れではなかったのでテストパターンと期待される結果を教えてもらえたのでわりとすぐに解決できましたが、それがなかったらかなり苦労したんじゃないかと思います。