#P14103. 【广度优先搜索1】走迷宫问题
-
ID: 1871
Tried: 465
Accepted: 117
Difficulty: 2
【广度优先搜索1】走迷宫问题
题目描述:
给定一个二维矩阵,表示一个迷宫,其中 1
表示墙壁,0
表示可以通行的道路。你有两个点,起点和终点,问是否存在一条从起点到终点的路径,使得你可以从起点走到终点。你可以上下左右四个方向移动,但不能穿过墙壁,也不能离开迷宫范围。坐标以行和列表示,均从0
开始,左上角坐标是 (0,0)
,右下角坐标是 (n-1,m-1)
。
输入:
- 第一行输入两个整数
n
和m
,表示迷宫的行数和列数 (1≤n,m≤100)。 - 接下来
n
行,每行包含m
个整数,表示迷宫的地图,其中0
表示通路,1
表示墙壁。 - 最后输入两个整数
x_1, y_1
和x_2, y_2
,表示起点和终点的坐标。
输出:
输出一个字符串,若从起点到终点存在路径,输出 "YES"
,否则输出 "NO"
。
示例1:
输入:
3 3
0 1 0
0 1 0
0 0 0
0 0 2 2
输出:
YES
示例2:
输入:
3 3
0 1 0
0 1 0
1 0 0
0 0 2 2
输出:
NO
【广度优先搜索1】走迷宫问题
前言
- 广度优先搜索(BFS)
- 队列的使用
1. 广度优先搜索(BFS)
广度优先搜索(Breadth-First Search,简称 BFS)是一种图或树的遍历或搜索算法。它从起始节点开始,首先访问所有相邻节点,然后对这些相邻节点的未访问邻居进行同样的操作,逐层向外扩展,直到遍历完所有节点或找到目标节点。
算法步骤:
- 初始化队列:创建一个空队列,用于存储待访问的节点。
- 起始节点入队:将起始节点入队。
- 循环以下操作,直到队列为空:
- 从队列中出队一个节点作为当前节点,并标记它为已访问。
- 访问当前节点的所有未被访问的邻居节点:
- 将这些邻居节点标记为已访问。
- 将这些邻居节点入队。
注意:队列的种类决定了BFS的使用范围,例如普通队列(先进先出)适用于层次遍历,优先队列(大根堆或小根堆)适用于最短路算法。本道题先学习普通队列的BFS。
为了更好得熟悉这个算法是实现步骤,让我们来看下面的这个例子。
在这个例子中,我们需要从节点1
开始使用BFS标记整个图,下面逐步拆解这个过程。
- 创建一个空的普通队列,我们把
节点1
作为起始节点
,标记节点1
,先让它进入队列。 - 接着我们开始执行BFS,从队列头部取出
节点1
,访问节点1
的所有未被访问的邻居节点(2,3)
,然后将节点2
和节点3
入队,并标记它们。 - 从队列头部取出
节点3
,标记节点3
,访问节点3
的所有未被访问的邻居节点(4,5)
,然后将节点4
和节点5
入队,并标记它们。4.重复上述步骤,直到队列为空,退出循环,到这里BFS就执行结束了。
这里大家可能会有疑惑,为什么不是取出队列的时候标记节点?因为这样会导致节点被重复入队,影响算法性能,例如下图,
节点1
为起始节点
,节点2
和节点3
都会把节点4
入队。
特点:
- 层次遍历:BFS 遍历时是逐层扩展,最先访问的节点距离起始节点最近,之后的节点距离逐渐增加。
- 最短路径:BFS 能够在无权图中找到从起点到目标节点的最短路径。
BFS 通常用于以下几种情况:
- 查找最短路径:在无权图中,BFS 可以找到从源节点到目标节点的最短路径。
- 图的连通性问题:例如,在图中查找所有与某个节点连接的节点。
- 层次遍历:例如,在树或图中逐层访问节点。
2. 队列的使用
Python 中,队列常常使用 collections.deque
来实现,它提供了一个高效的双端队列,可以从队列两端进行插入和删除操作。与列表相比,deque
在两端操作的时间复杂度为 O(1),而列表的两端操作为 O(n)。
双端队列相比普通队列,两边都能出队和入队,使用更加方便。
常用方法:
append(value)
:将元素添加到队列的末尾。popleft()
:移除队列的头部元素并返回它。appendleft(value)
:将元素添加到队列的头部。len()
:获取队列的大小。
示例代码:
from collections import deque
# 创建一个空的队列
q = deque()
# 入队操作:append
q.append(10) # 向队列中添加元素 10
q.append(20) # 向队列中添加元素 20
q.append(30) # 向队列中添加元素 30
# 获取队列的大小
print("队列大小:", len(q)) # 输出 3
# 查看队列的头部元素:[0] 直接取值
print("队列头部元素:", q[0]) # 输出 10
# 出队操作:popleft
q.popleft() # 移除队列中的第一个元素
# 再次查看队列的头部元素
print("新的队列头部元素:", q[0]) # 输出 20
# 判断队列是否为空:empty
if len(q) == 0:
print("队列为空")
else:
print("队列不为空")
3. 题解
题面描述
给定一个二维矩阵表示的迷宫,迷宫中有墙壁和通路。矩阵中的 1
表示墙壁,0
表示通路。起点和终点的位置也被给定,问是否存在一条从起点到终点的路径,可以在迷宫中移动。你可以上下左右四个方向移动,但不能穿越墙壁。
解题思路
-
广度优先搜索(BFS):
- 由于该问题是一个典型的路径搜索问题,可以使用广度优先搜索(BFS)来找到从起点到终点的最短路径。BFS 是一种无权图中查找最短路径的常用算法,它能够保证在搜索过程中先访问的节点就是从起点出发到达该节点的最短路径。
- 我们使用一个队列来保存当前可以访问的节点。每次从队列中取出一个节点并遍历其四个邻居(上、下、左、右)。
- 对于每个邻居,如果它是通路并且没有被访问过,就将其加入队列并标记为已访问。
- 如果在搜索过程中,队列中某个节点的坐标等于终点的坐标,则说明找到了从起点到终点的路径,可以输出
YES
。
-
BFS 过程:
- 初始时将起点
(x1, y1)
放入队列,并标记为已访问。 - 从队列中取出当前节点,检查其四个方向的邻居。如果邻居符合条件(即在迷宫范围内、未被访问、且是通路),则将该邻居加入队列。
- 初始时将起点
# 检查新位置是否在迷宫范围内,且是通路,且未被访问过
if new_x >= 0 and new_x < n and new_y >= 0 and new_y < m and \
maze[new_x][new_y] == 0 and not visited[new_x][new_y]:
q.append((new_x, new_y)) # 将新节点加入队列
visited[new_x][new_y] = True # 标记该节点为已访问
- 如果在任何一次的队列操作中找到了终点
(x2, y2)
,则立即输出YES
并结束搜索。 - 如果 BFS 执行完毕后没有找到终点,则输出
NO
。
-
边界与约束:
- 在 BFS 搜索过程中,需要确保每次访问的邻居不越界且未访问过。
- 对于每个节点的访问,都需要检查该节点是否是墙壁或已经访问过,以防止死循环和重复访问。
-
时间复杂度:
- 由于每个节点最多被访问一次,因此时间复杂度是
O(n * m)
,其中n
是迷宫的行数,m
是迷宫的列数。
- 由于每个节点最多被访问一次,因此时间复杂度是
代码实现
from collections import deque
def bfs_maze(maze, start, end, n, m):
# 定义四个移动方向:上、下、左、右
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
# 初始化访问数组,所有位置初始为未访问
visited = [[False] * m for _ in range(n)]
# 使用队列进行 BFS
q = deque()
x1, y1 = start
x2, y2 = end
# 起点入队,并标记为已访问
q.append((x1, y1))
visited[x1][y1] = True
while q:
x, y = q.popleft()
# 如果当前点是终点,返回 True
if (x, y) == (x2, y2):
return True
# 尝试四个方向移动
for i in range(4):
new_x, new_y = x + dx[i], y + dy[i]
# 检查新位置是否在迷宫范围内,且是通路,且未被访问过
if 0 <= new_x < n and 0 <= new_y < m and \
maze[new_x][new_y] == 0 and not visited[new_x][new_y]:
q.append((new_x, new_y)) # 将新节点加入队列
visited[new_x][new_y] = True # 标记为已访问
return False
def main():
# 输入迷宫的行数和列数
n, m = map(int, input().split())
# 输入迷宫地图
maze = [list(map(int, input().split())) for _ in range(n)]
# 输入起点和终点的坐标
x1, y1, x2, y2 = map(int, input().split())
# 检查起点和终点是否有效
if maze[x1][y1] == 1 or maze[x2][y2] == 1:
print("NO")
return
# 调用 BFS 检查是否能找到路径
if bfs_maze(maze, (x1, y1), (x2, y2), n, m):
print("YES")
else:
print("NO")
if __name__ == "__main__":
main()