昨天，玩推箱子游戲玩到第四關實在過不去了，用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 閱讀(1522)
評論(0) 編輯 收藏 引用