Python中使用BFS和DFS解决迷宫问题

2023-04-11 00:00:00 python 解决 迷宫

迷宫问题可以被看作是从一个起点到达一个终点的路径问题，可以使用广度优先搜索（BFS）和深度优先搜索（DFS）算法来解决。

BFS的核心思想是以广度优先的方式依次访问所有可能的节点，即先访问距离起点最近的节点，并使用队列来存储节点。当到达终点或者所有节点都被访问时，算法结束。

DFS的核心思想是先访问某个节点，然后递归访问它的所有邻居节点，直到到达终点或者所有节点都被访问。在实现中，可以使用栈来存储节点。

下面我们以一个简单的迷宫为例，使用BFS和DFS算法来求解迷宫的解法。

迷宫地图：

0 0 0 0 0 0 
0 1 0 1 1 0 
0 1 0 0 1 0 
0 1 1 1 1 0 
0 0 0 0 0 0

其中0表示可以通过的路径，1表示障碍物，起点位置为(1,1)，终点位置为(4,4)。

BFS代码演示：

from queue import Queue

# 迷宫地图
maze = [
    [0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 1, 0],
    [0, 1, 0, 0, 1, 0],
    [0, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0]
]

# 起点和终点
start = (1, 1)
end = (4, 4)

# 定义四个方向
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]


def bfs():
    q = Queue()
    q.put(start)

    visited = set()
    visited.add(start)

    while not q.empty():
        cur_pos = q.get()

        if cur_pos == end:
            return True

        for direction in directions:
            new_pos = (cur_pos[0] + direction[0], cur_pos[1] + direction[1])

            if 0 <= new_pos[0] < len(maze) and 0 <= new_pos[1] < len(maze[0]) and maze[new_pos[0]][new_pos[1]] == 0 and new_pos not in visited:
                q.put(new_pos)
                visited.add(new_pos)

    return False


result = bfs()
if result:
    print("可以到达终点")
else:
    print("不能到达终点")

DFS代码演示：

# 迷宫地图
maze = [
    [0, 0, 0, 0, 0, 0],
    [0, 1, 0, 1, 1, 0],
    [0, 1, 0, 0, 1, 0],
    [0, 1, 1, 1, 1, 0],
    [0, 0, 0, 0, 0, 0]
]

# 起点和终点
start = (1, 1)
end = (4, 4)

# 定义四个方向
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]


def dfs(cur_pos, visited):
    visited.add(cur_pos)

    if cur_pos == end:
        return True

    for direction in directions:
        new_pos = (cur_pos[0] + direction[0], cur_pos[1] + direction[1])

        if 0 <= new_pos[0] < len(maze) and 0 <= new_pos[1] < len(maze[0]) and maze[new_pos[0]][new_pos[1]] == 0 and new_pos not in visited:
            if dfs(new_pos, visited):
                return True

    return False


result = dfs(start, set())
if result:
    print("可以到达终点")
else:
    print("不能到达终点")

以上代码展示了如何使用BFS和DFS算法解决迷宫问题，BFS算法通过队列实现，DFS算法通过递归实现，根据具体需求选择不同的算法。

相关文章