Python走迷宫，递归

递归走迷宫，练手。

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

#!/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_)

基本上没什么说的，主要是递归的思想。

迷宫的形式：0是墙，1是可走路径，2代表被走过的路。maze_用来显示路径，直观些。

如果我早些在最后调用findDest函数时加上条件判断来确认findDest的返回值，我应该能早些发现isDest里字符的错误。开始检查了几遍函数，居然都没发现，眼神不行了。今早还以为是visit函数的调用位置有问题，胡乱试是不会有结果的。