昨天，玩推箱子游戏玩到第四关实在过不去了，用C++写了一个BFS+DP的算法求解。结果是170步。
其实我一开始是想用python来写的，但是觉得二位矩阵这个东西很难用python来描述，于是作罢。写完后看看自己的代码，觉得恶心的不行。于是在网上搜索了一下，发现大牛居然可以把python写得如此之简洁，又一次拜服了！
《
用python求解迷宫问题》
http://v.youku.com/v_show/id_XMTcwMzc5MTAw.html下面是我按照视频里面敲的python代码，我的实在垃圾就不拿出来了。
这段代码最然我感到惊叹的是他对迷宫模型的表示方式，二位矩阵就如此轻描淡写的表示出来！
ps,网页代码的对齐有点问题。
1
ASCII_MAZE = '''
2+----------------+
3| | | |
4| | +--+ ----+ | |
5| | | | |
6| | +---- | | |
7| | | | | E
8+---+ | | | | |
9S | | | |
10+------+--+--+---+
11'''
12PATH,START,EXIT,VISITED, SOLUTION = " SE.o"
13
14class Maze():
15 def __init__(self, ascii_maze):
16 self.maze = [list(row) for row in ascii_maze.splitlines()]
17 self.start_x = [row.count(START) for row in self.maze].index(1)
18 self.start_y = self.maze[self.start_x].index(START)
19
20 def __repr__(self):
21 return "\n".join("".join(row) for row in self.maze)
22
23 def solve(self, x = None, y = None):
24 if x == None:
25 x = self.start_x
26 y = self.start_y
27
28 if self.maze[x][y] in (PATH, START):
29 self.maze[x][y] = VISITED
30 if self.solve(x + 1, y) or self.solve(x - 1, y)\
31 or self.solve(x, y +1) or self.solve(x, y -1):
32 self.maze[x][y] = SOLUTION
33 return True
34 elif self.maze[x][y] == EXIT:
35 return True
36 return False
37
38
39if __name__ == "__main__":
40 import sys
41 sys.setrecursionlimit(10000)
42 m = Maze(ASCII_MAZE)
43 if m.solve():
44 print m
45
46
posted on 2010-07-18 17:20
margin 阅读(1500)
评论(0) 编辑 收藏 引用