Python走迷宫，递归

nix posted @ 2012年2月25日 08:53 in Python with tags 迷宫递归 , 4304 阅读

递归走迷宫，练手。

23下午就写好的，可是测试几种不同的迷宫后，发现有个Bug，我以为算法有问题，今早才发现，原来是isDest函数里r和c都写成r了，拷贝out函数的语句再改写造成的悲剧。

maze.py
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117	`#!/usr/bin/env python` `# author: @nixzhu` `# date: 2012.02.25` `# description: Maze, use recursive.` `# Door is (7, 7), as follow shows` `# license: GPL` `maze` `=` `[` `[1,1,0,0,0,0,1,0],` `[0,1,0,0,0,1,1,0],` `[0,1,1,1,1,1,0,0],` `[1,1,0,0,0,1,0,0],` `[1,0,0,0,0,1,1,1],` `[1,1,1,1,1,1,0,0],` `[0,0,0,1,0,1,1,1],` `[0,0,0,1,0,1,0,1]` `]` `maze_` `=` `[` `[0,0,0,0,0,0,0,0],` `[0,0,0,0,0,0,0,0],` `[0,0,0,0,0,0,0,0],` `[0,0,0,0,0,0,0,0],` `[0,0,0,0,0,0,0,0],` `[0,0,0,0,0,0,0,0],` `[0,0,0,0,0,0,0,0],` `[0,0,0,0,0,0,0,0]` `]` `def` `showMaze(maze):` `print` `'-----------------S'` `for` `line` `in` `maze:` `for` `l` `in` `line:` `print` `l,` `print` `''` `print` `'-----------------E'` `def` `findDest(p={'r':0,` `'c':0}):` `if` `out(p):` `#print '>> ++ out\t', p['r'], p['c']` `return` `False` `#print '>> -- out\t', p['r'], p['c']` `if` `isWall(p):` `return` `False` `if` `wasVisited(p):` `return` `False` `visit(p)` `if` `isDest(p):` `print` `'('+str(p['r'])+', '+str(p['c'])+')'` `maze_[p['r']][p['c']]` `=` `'#'` `return` `True` `else:` `if` `findDest(p=left(p)):` `print` `'('+str(p['r'])+', '+str(p['c'])+')'` `maze_[p['r']][p['c']]` `=` `'#'` `return` `True` `if` `findDest(p=up(p)):` `print` `'('+str(p['r'])+', '+str(p['c'])+')'` `maze_[p['r']][p['c']]` `=` `'#'` `return` `True` `if` `findDest(p=right(p)):` `print` `'('+str(p['r'])+', '+str(p['c'])+')'` `maze_[p['r']][p['c']]` `=` `'#'` `return` `True` `if` `findDest(p=down(p)):` `print` `'('+str(p['r'])+', '+str(p['c'])+')'` `maze_[p['r']][p['c']]` `=` `'#'` `return` `True` `return` `False` `def` `out(p={'r':0,` `'c':0}):` `if` `p['r'] <` `0` `or` `p['r'] >` `7:` `return` `True` `if` `p['c'] <` `0` `or` `p['c'] >` `7:` `return` `True` `return` `False` `def` `isWall(p={'r':0,` `'c':0}):` `if` `maze[p['r']][p['c']]` `==` `0:` `return` `True` `else:` `return` `False` `def` `wasVisited(p={'r':0,` `'c':0}):` `if` `maze[p['r']][p['c']]` `==` `2:` `return` `True` `else:` `return` `False` `def` `isDest(p={'r':0,` `'c':0}):` `if` `p['r']` `==` `7` `and` `p['c']` `==` `7:` `return` `True` `else:` `return` `False` `def` `visit(p={'r':0,` `'c':0}):` `maze[p['r']][p['c']]` `=` `2` `def` `left(p={'r':0,` `'c':0}):` `return` `{'r':p['r'],` `'c':p['c']-1}` `def` `right(p={'r':0,` `'c':0}):` `return` `{'r':p['r'],` `'c':p['c']+1}` `def` `up(p={'r':0,` `'c':0}):` `return` `{'r':p['r']-1,` `'c':p['c']}` `def` `down(p={'r':0,` `'c':0}):` `return` `{'r':p['r']+1,` `'c':p['c']}` `if` `__name__=='__main__':` `showMaze(maze)` `if` `not` `findDest(p={'r':0,` `'c':0}):` `# Enter is (0, 0)` `print` `"No, can't find destination"` `else:` `print` `"Yes, find destination"` `showMaze(maze)` `showMaze(maze_)`