本帖最后由 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]]
复制代码
解决方法是用copy模块中的deepcopy函数,如下
- >>> 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)
复制代码 key参数:将前面序列中的每个元素带入key参数指向的函数,将返回值最大的那个元素return~~有点绕
-*--*--*--*--*--*--*--*--*--*--*---*--*--*--*--*--*--*--*--*--*--*---*--*--*--*--*--*--*--*--*--*--*---*--*--*--*--*--*--
在用pycharm调试时如果注释或者程序中有中文里要在代码头部加上# -*- coding: utf-8 -*-,不然编译时会出现错误
|