基于递归的回溯算法：求解迷宫所有路径

1. 一般来讲，回溯算法的格式如下：

result = []

def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return

    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

2. 经典的寻找迷宫所有路径问题：

题目

3. 输入数据格式

image.png

样例如下：

image.png

4. 完整代码

# -*- codeing = utf-8 -*-

# 路径方向：向右---------------------向上----------------------向左----------------------向下
# deals = [lambda x, y: (x + 1, y), lambda x, y: (x, y + 1), lambda x, y: (x - 1, y), lambda x, y: (x, y - 1)]

deals = [lambda x, y: (x - 1, y), lambda x, y: (x, y + 1)]

def permute(start, end, maze):
    res = []  # 记录所有路径
    path = []  # 能走到终点的路径
    def backtrack(start, end, maze):
        path.append(start)  # start为开始路径
        if len(path) > 0:
            path_node = path[-1]  # 记录path上一个路径点
            if path_node == end:
                print("path =", path)
                res.append(1)  # 记录路径个数
                path.pop()
                return  # 在递归循环当中，return结束的是当前递归调用，并不会结束所有递归调用
            for index, deal in enumerate(deals):
                # next_node=(x,y) 路径坐标----元组的形式
                next_node = deal(path_node[0], path_node[1])
                # 出界状况和遇到1的情况
                if next_node[0] < 0 or next_node[1] > end[1] or maze[next_node[0]][next_node[1]] == 1:
                    if index == len(deals) - 1:
                        path.pop()
                        return
                    else:
                        continue
                # 未出界
                else:
                    backtrack(next_node, end, maze)
                    if index == len(deals) - 1:
                        path.pop()

    backtrack(start, end, maze)
    return res

if __name__ == '__main__':
    [a, b] = list(map(int, input().split()))  # a为行,b为列
    maze = []  # 迷宫本身
    for i in range(a):
        maze.append([int(j) for j in input().split()])

    result = permute((a - 1, 0), (0, b - 1), maze)
    print(len(result))

5. 总结

Python代码运行速度比较慢，有几个case总是超时，当然本代码还有优化的空间