迷路を解いてみた

http://okajima.air-nifty.com/b/2010/01/post-abc6.html

これを解いてみた。
50分かかりました。

# coding: utf-8

import sys

data = """**************************
*S* *                    *
* * *  *  *************  *
* *   *    ************  *
*    *                   *
************** ***********
*                        *
** ***********************
*      *              G  *
*  *      *********** *  *
*    *        ******* *  *
*       *                *
**************************"""

# 各マスの距離を算出
def solve(x, y, maze):
	# 現在のマスの上下左右を調べる
	for [dx, dy] in [[x, y-1], [x+1, y], [x, y+1], [x-1, y]]:
		if maze[dy][dx] > maze[y][x] + 1:
			maze[dy][dx] = maze[y][x] + 1
			solve(dx, dy, maze)

# ゴールから逆順にたどって$マークを付ける
def route(x, y, maze, out):
	# 現在のマスの上下左右を調べる
	for [dx, dy] in [[x, y-1], [x+1, y], [x, y+1], [x-1, y]]:
		if maze[dy][dx] == maze[y][x] - 1 and maze[dy][dx] > 0:
			out[dy][dx] = "$"
			route(dx, dy, maze, out)
			break

wall = -1 # 壁
inf = 100000 # 探索前の初期値

maze = [] # 距離データ
out = [] # 出力データ
start = [] # スタート位置
goal = [] # ゴール位置

# 入力をリスト構造に変換
iy = 0
ix = 0
for line in data.splitlines():
	lmaze = []
	lout = []
	for c in line:
		lout.append(c)
		if c == "*":
			lmaze.append(wall)
		else:
			lmaze.append(inf)
			if c == "S":
				start = [ix, iy]
			elif c == "G":
				goal = [ix, iy]
		ix += 1
	maze.append(lmaze)
	out.append(lout)
	iy += 1
	ix = 0


# 距離を算出
[x, y] = start
maze[y][x] = 0
solve(x, y, maze)

# ゴールから逆順に辿る
[x, y] = goal
route(x, y, maze, out)

# 標準出力に出力
for l in out:
	for c in l:
		sys.stdout.write(c)
	sys.stdout.write("\n")

↓出力結果

**************************
*S* * $$$$               *
*$* *$$* $*************  *
*$* $$*  $$************  *
*$$$$*    $$$$$          *
**************$***********
* $$$$$$$$$$$$$          *
**$***********************
* $$$$$* $$$$$$$$$$$$$G  *
*  *  $$$$*********** *  *
*    *        ******* *  *
*       *                *
**************************

• printだとスペースが入ってしまうのでsys.stdout.writeに修正
• xとy逆だった…