先声明思路是学“冲就完事”博主的题解的(“真正python 迷宫最短路径解法(华为机试)”),
把原帖贴上:https://blog.nowcoder.net/n/a3e0ea7fbf3746f6b342fe0d26d7fd5b?f=comment
他的代码很详细,大家可以去琢磨一下他的思路。
很好的一道递归题,下面先对递归做个小总结。
首先递归就是函数自己调用自己,当然要有结束嵌套的情况,不能一直调用。函数调用的情况可以看作是压栈,最后调用的那一次先有结果或返回,然后返回倒数第二次,最后返回到最初的函数调用。
那么遵循以上原则,对此题思路做个解释。
首先是有迷宫的输入,此外我们对路劲和走过的点要做记录,这里设为path,points。
然后就是函数部分,我们有起点(0,0),这个作为最初的函数输入,进入函数后第一步先判断下一个可以走的点和把当前点记作走过的点,我们为了简洁递归里的代码段,再嵌套一个寻找下一个点的函数,返回的是下一个可能的点的集合k(以序列的形式),然后如果没有下一个可能的点了(也就是路堵死了),就结束函数,如果有下一个点的可能,则让路径添加该点,判断是否到达了终点。如果到达了,则判断路径长度是否最短,最短的话则把结果路径修改(res),否则不变。没有的话,对路径和走过的点进行一个浅复制,递归调用函数。
在函数返回的时候,如果在返回的点处还有另外可能的点,则修改路径的最后一项(也就是该点第一次选择的路)。可以这样修改的原因是浅复制,后续调用的时候不会改变当前路径的记录,详细想了解的可以去搜浅复制。
while True: try: n, m = [int(x) for x in input().split()] maze = [] for i in range(n): maze.append([int(x) for x in input().split()]) points = [] for i in range(n): points.append([]) for j in range(m): points[i].append(0) path = [] def get_points(i,j,maze,points): # print('test3',i,j) k = [] if(0 <= i+1 < n and maze[i+1][j] == 0 and points[i+1][j] == 0): k.append([i+1,j]) if(0 <= i-1 < n and maze[i-1][j] == 0 and points[i-1][j] == 0): k.append([i-1,j]) if(0 <= j+1 < m and maze[i][j+1] == 0 and points[i][j+1] == 0): k.append([i,j+1]) if(0 <= j-1 < m and maze[i][j-1] == 0 and points[i][j-1] == 0): k.append([i,j-1]) # print('test4',k) return k def get_path(i,j,maze,path,points): global res k = get_points(i,j,maze,points) points[i][j] = 1 # print('test2',k) if(len(k) > 0): for num1 in range(len(k)): if(num1 == 0): path.append(k[num1]) else: path[-1] = k[num1] if(k[num1] == [n - 1,m - 1]): if(len(res) == 0 or len(path) < len(res)): res = path else: tpath = path.copy() tpoints = points.copy() # print('test1',tpath,tpoints) get_path(k[num1][0],k[num1][1],maze,tpath,tpoints) global res res = [] get_path(0,0,maze,path,points) print('(0,0)') for num2 in range(len(res)): print('(%d,%d)'%(res[num2][0],res[num2][1])) except: break