本文共 2593 字，大约阅读时间需要 8 分钟。

用队列解决迷宫问题

1. 概述

    昨天介绍了用栈解决迷宫问题，具体可以去看上一篇博客

今天讲讲用队列解决迷宫问题。

2. 思路

队列——广度优先搜索

思路:从一个节点开始，寻找所有接下来能继续走的点，继续不断寻找，直到找到出口。 使用队列存储当前正在考虑的节点 区别: 用队列和栈解决迷宫问题最大的区别在于，栈利用了深度优先搜索的思想，而队列利用了广度优先搜索的思想 具体的迷宫问题也可以去看上一博文，这里展示一张图:

代码:

'''TOPIC: 用队列解决迷宫问题author: Bluetime: 2020-08-12QQ: 2458682080'''from collections import dequemaze = [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1],[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],[1, 0, 0, 1, 0, 0, 0, 1, 0, 1],[1, 0, 0, 0, 0, 1, 1, 0, 0, 1],[1, 0, 1, 1, 1, 0, 0, 0, 0, 1],[1, 0, 0, 0, 1, 0, 0, 0, 0, 1],[1, 0, 1, 0, 0, 0, 1, 0, 0, 1],[1, 0, 1, 1, 1, 0, 1, 1, 0, 1], [1, 1, 0, 0, 0, 0, 0, 0, 0, 1],[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]dirs = [    lambda x,y: (x, y - 1),     lambda x,y: (x + 1, y),     lambda x,y: (x, y + 1),     lambda x,y: (x - 1, y)]def print_r(path):    cur_node = path[-1]    real_path = []    while cur_node[2] != -1:        real_path.append(cur_node[0:2])        cur_node = path[cur_node[2]]    real_path.append(cur_node[0:2])    real_path.reverse()    for node in real_path:        print(node)def maze_path_queue(x1, y1, x2, y2):    queue = deque()    queue.append((x1, y1, -1))    path = []    # 队空了，没有路    while len(queue) > 0:        cur_node = queue.popleft()        path.append(cur_node)        if cur_node[0] == x2 and cur_node[1] == y2:            print_r(path)            return True        for dir in dirs:            next_node = dir(cur_node[0], cur_node[1])            if maze[next_node[0]][next_node[1]] == 0:                # 后续节点进队，记录哪个节点带它来的                queue.append((next_node[0], next_node[1], len(path)-1))                maze[next_node[0]][next_node[1]] = 2    else:        print("走投无路，无路可走")        return Falsemaze_path_queue(1, 1, 8, 8)

结果:

(1, 1)(2, 1)(3, 1)(4, 1)(5, 1)(5, 2)(5, 3)(6, 3)(6, 4)(6, 5)(7, 5)(8, 5)(8, 6)(8, 7)(8, 8)

其实用队列解决和用栈解决的代码中，最大却别在于这里:

# 用队列解决 for dir in dirs:            next_node = dir(cur_node[0], cur_node[1])            if maze[next_node[0]][next_node[1]] == 0:                # 后续节点进队，记录哪个节点带它来的                queue.append((next_node[0], next_node[1], len(path)-1))                maze[next_node[0]][next_node[1]] = 2# 用栈解决for dir in dirs:            next_node = dir(current_node[0], current_node[1])            # 如果下一个节点能走            if maze[next_node[0]][next_node[1]] == 0:                stack.append(next_node)                maze[next_node[0]][next_node[1]] = 2  # 表示已经走过                break

用栈解决的加了break，用队列解决没有加break。

栈——深度优先搜索: 只要在当前位置current_node找到一点next_node可以继续往下的，就直接将current_node改为next_node，就这样先把一条路走到黑，如果最后发现走不通，再返回，走其他路。 队列——广度优先搜索: 在当前位置current_node找到所有可以走的next_node，然后再将所有的next_node的下一步可以走的点也找出来，直到找到终点！

转载地址：http://nbiwi.baihongyu.com/