本帖最后由 lightninng 于 2015-3-21 21:22 编辑
昨天晚上看到某版主之前的一个贴子，讲的是迷宫问题，记得当年在学数据结构的时候好像也有（虽然不是重点没怎么好好看），觉得挺有意思，就想花点时间用python写一下，结果竟然用了一个上午，不得不说，好的编程习惯很重要，注释，调试的时候的方法，慢慢积累吧以下是问题
"""
迷宫没有墙壁，但是每条边的路被坑包围。如果一个玩家掉在坑里的话，他们就丢失了。迷宫是用矩阵来表示（含有列表的列表）: 1是坑，0的路径的一部分。 迷宫的大小是12×12，外界都是坑。
玩家在点（1,1）开始。出口是在点（10,10）。 你需要找到通过迷宫的路径。 玩家只能通过四个方向移动 南（下 [1,0]），北（上 [-1,0]）， 东（右[0,1]），西（左[0，-1]）。这条路线被
描述成由不同的字符组成的字符串：“S”=南，“N”=北，“E”=东，和“W”=西。
"""
maze_one = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1],
[1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1],
[1, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1],
[1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1],
[1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
maze_two = [
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
[1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1],
[1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1],
[1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1],
[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
]
最终的代码是def search_out(maze_num):
"""寻找走出迷宫的路径并打印"""
def check(x, y):
#返回(x, y)周围除来路之外可走的位置组成的列表
next_pos = []
for each in [(x, y+1), (x+1, y), (x, y-1), (x-1, y)]:
if maze_num[each[0]][each[1]] == 0:
next_pos.append(each)
return next_pos # 用于检查i,j点处可行处有几处
def path_d(path):
#按位置路线打印每步所走的方向
dict_dir = {(0, 1): "东", (1, 0): "南", (0, -1): "西", (-1, 0): "北"}
length = len(path)
for k in range(length - 1):
print(dict_dir[(path[k+1][0] - path[k][0], path[k+1][1] - path[k][1])], "->", end = "")
print(dict_dir[(10 - path[-1][0], 10 - path[-1][1])])
i = j = 1
stack_branch = [[(i, j), check(i, j)]] # 用于记录岔路口
stack_path = [] # 用于记录走过的路径
min_path = []
count = 0
while stack_branch:
maze_num[i][j] = 1
stack_path.append((i, j))
(i, j) = (stack_branch[-1][1]).pop()
if len(stack_branch[-1][1]) == 0:
stack_branch.pop()
check_dir = []
while True:
check_dir = check(i, j)
if len(check_dir) != 1 or (i, j) == (10, 10):
break # 返回上一个路口
else:
stack_path.append((i, j))
maze_num[i][j] = 1
[(i, j)] = check_dir # 继续前进
if len(check_dir) > 1:
stack_branch.append([(i, j), check_dir])
else:
branch_temp = [each[0] for each in stack_branch]
if (i, j) == (10, 10):
#下面的代码改为print(stack_path)就可以打印所有可能的路径
if len(stack_path) < len(min_path) or len(min_path) == 0:
min_path = stack_path[:]
if len(stack_branch) != 0:
while (i, j) not in branch_temp:
(i, j) = stack_path.pop()
maze_num[i][j] = 0
maze_num[i][j] = 0
path_d(min_path)
1、每次循环结束要保证所处的条件都一致，这里就是当while stack_branch:循环每一次结束时，要求i,j处在岔路点上，且该岔路点并未标记为已走过
2、在列表拷贝时，min_path = stack_path和min_path =stack_path[:]的区别，用前者时当stack_path改变，min_path也会改变，导致最后stack_path.pop()报错，另外在查这个问题时看到后一种写法当stack_path内元素有列表时，min_path内部的列表会随stack_path内的列表而改变：如>>> a=[1,[2]]
>>> b=a[:]
>>> b
[1, [2]]
>>> a[1].append(3)
>>> a
[1, [2, 3]]
>>> b
[1, [2, 3]]
>>> import copy
>>> a=[1,[2]]
>>> b=copy.deepcopy(a)
>>> b
[1, [2]]
>>> a[1].append(3)
>>> a
[1, [2, 3]]
>>> b
[1, [2]]
-*--*--*--*--*--*--*--*--*--*--*---*--*--*--*--*--*--*--*--*--*--*---*--*--*--*--*--*--*--*--*--*--*---*--*--*--*--*--*--
比较懒，刚看到了[checkio]---找到出现频率最高的字母---这个贴子，自己只是大概想了下没有去实现 ，不过大神的方法记录下，以后说不定有用~~import string
def checkio(text):
text = text.lower()
return max(string.ascii_lowercase, key=text.count)
-*--*--*--*--*--*--*--*--*--*--*---*--*--*--*--*--*--*--*--*--*--*---*--*--*--*--*--*--*--*--*--*--*---*--*--*--*--*--*--
在用pycharm调试时如果注释或者程序中有中文里要在代码头部加上# -*- coding: utf-8 -*-，不然编译时会出现错误
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2015-3-21 14:28:50
置顶卡
千斤顶
显身卡
楼主
发表于 2015-4-3 08:35:45