A*で解いてみた。距離はマンハッタン使った。
maze = ["**************************",
"*S* * *",
"* * * * ************* *",
"* * * ************ *",
"* * *",
"************** ***********",
"* *",
"** ***********************",
"* * G *",
"* * *********** * *",
"* * ******* * *",
"* * *",
"**************************"]
start = ()
goal = ()
max = len(maze) + len(maze[0])
for (h,line) in enumerate(maze):
for (w,word) in enumerate(line):
if word == 'S': start = (h,w)
elif word == 'G': goal = (h,w)
checked = [start]
sol = [start]
def add_route(r):
(h,w) = r[-1]
cand = [c for c in [(h+1,w),(h-1,w),(h,w+1),(h,w-1)] if c not in checked and not_wall(c)]
if len(cand) == 0:
return r[:-1]
else:
sol = (); cost = max
for c in cand:
c_cost = calc_cost(c)
if c_cost < cost:
cost = c_cost
sol = c
r.append(sol)
checked.append(sol)
return r
def not_wall(p): (h,w) = p; return maze[h][w] != '*'
def calc_cost(p): return (abs(goal[0]-p[0]) + abs(goal[1]-p[1]))
def check_goal(sol): return sol[-1] != goal
def draw_sol(sol):
solved_maze = ''
for (h,line) in enumerate(maze):
for (w,word) in enumerate(line):
if (h,w) in sol[1:-1]:
solved_maze += '$'
else:
solved_maze += word
solved_maze += '\n'
return solved_maze
while check_goal(sol): sol = add_route(sol)
print draw_sol(sol)
実行結果
$ python maze_aster.py
**************************
*S* * $$$ *
*$* *$$*$ ************* *
*$* $$* $ ************ *
*$$$$* $$$$$$$ *
**************$***********
* $$$$$$$$$$$$$ *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G *
* * $$$ *********** * *
* * ******* * *
* * *
**************************