走迷宫
提交数: 529, 通过率: 50.09%, 平均分: 57.23
题目描述:
给你一个 m*n 的迷宫矩阵maze，矩阵中有空格子（用1表示，可通行）和墙（用0表示，不可通行），在迷宫中通行的每一步移动操作，你可以往 上，下，左 或者 右 移动一个格子，但不能进入墙所在的格子。
寻找最近出口位置的思路与算法：（广度优先搜索）
预设： 0墙 1空格子 2已探索
在广度优先搜索的过程中，我们在队列中保存(cx, cy, d)三元组，其中 (cx,cy)为当前的行列坐标，d为当前坐标相对入口的距离(即需要移动的步数)。
当我们遍历至(cx,cy)时，我们枚举它上下左右的相邻坐标(nx,ny)。此时可能有三种情况：
①(nx,ny)不属于迷宫坐标或为墙，此时无需进行任何操作；
②(nx,ny)为迷宫的出口（在迷宫边界且不为墙），此时应返回nx,ny,d+1，即该出口的坐标以及相对入口的距离作为答案。
③(nx,ny)为空格子且不为出口，此时应将新坐标设置为已探索，并将其对应的三元组 (nx,ny,d+1)加入队列。
此外，为了避免重复遍历，我们可以将所有遍历过的坐标对应迷宫矩阵的值改为2。
最终，如果不存在到达出口的路径，我们返回-1作为答案。
输入格式:
第一行输入迷宫的行数、列数
接着输出迷宫
最后一次两个数，是迷宫的入口坐标
输出格式:
输出最少的步数
数据范围:
迷宫范围不大于20 * 20 的迷宫
样例输入:
10 10 0,0,0,0,0,0,0,0,1,0 1,1,1,0,1,1,1,0,1,0 0,1,1,0,1,1,1,0,1,1 0,1,1,1,1,0,0,1,1,0 0,1,0,0,0,1,1,1,1,0 0,1,1,1,0,1,1,1,1,0 0,1,0,1,1,1,0,1,1,0 0,1,0,0,0,1,0,0,0,0 0,0,1,1,1,1,1,1,1,1 0,0,0,1,0,0,0,0,0,0 1 0
样例输出:
15
提示:
要求理解广搜算法及其队列的基本操作。
完善程序。
import queue
BLOCKED,OPENED,PASSED = 0, 1, 2
# 判断坐标有效性
def valid(maze,pos):
if (0<=pos[0]<m and 0<=pos[1]<n and ___________(1)___________ ):
return True
else:
return False
def findExit(maze, entry):
# 上下左右四个相邻坐标对应的行列变化量
dx = [-1, 1, 0, 0] #上下左右，行方向的增量值
dy = [0, 0, -1, 1] #上下左右，列方向的增量值
q = queue.Queue( maxsize=100 ) #maxsize 省略或等于0，表示不限制队列的容量
q.put([entry[0], entry[1], 0]) #首先把入口的坐标放入队列并标记
maze[entry[0]][entry[1]] = PASSED #入口的坐标放入队列后，并上已走过的标记
while q.qsize()>0:
cx, cy, d = q.get() #弹出队列中的数据
# 遍历四个方向相邻坐标
for k in range(4):
__________(2)____________ # 从[cx, cy]位置出发，在k方向上扩展新位置
if valid(maze,(nx,ny)):
# 新坐标合法且不为墙
if nx == 0 or nx == m - 1 or ny == 0 or ny == n - 1:
# 新坐标为出口，返回坐标、距离
return nx,ny,d+1
# 新坐标为空格子且不为出口，修改为墙并加入队列
__________(3)____________ #新位置加入队列时，要标上已走过的标记
q.put([nx, ny, d + 1])
# 不存在到出口的路径，返回 -1
return -1, -1, -1
'''
maze=[ [0,0,0,0,0,0,0,0,1,0],
[1,1,1,0,1,1,1,0,1,0],
[0,1,1,0,1,1,1,0,1,1],
[0,1,1,1,1,0,0,1,1,0],
[0,1,0,0,0,1,1,1,1,0],
[0,1,1,1,0,1,1,1,1,0],
[0,1,0,1,1,1,0,1,1,0],
[0,1,0,0,0,1,0,0,0,0],
[0,0,1,1,1,1,1,1,1,1],
[0,0,0,1,0,0,0,0,0,0] ]
'''
m, n = map(int, input().split() ) #迷宫的行数，列数
maze = [ ]
for i in range( m ): #读入迷宫
line = input().strip()
a = list( map( int , line.split(',') ) )
maze.append( a )
x, y = map( int, input().split() ) #读入迷宫的入口
entry=[ x, y] #预设的迷宫入口
exit_pos_x, exit_pos_y, steps = __________(4)___________ #开始广搜，返回找到的出口及最小步数
if steps==-1:
print("No Path!")
else:
print( steps )
#exit_pos=[exit_pos_x,exit_pos_y]
#print('入口:',entry,' 最近出口位置:',exit_pos,' 最少移动步数:',steps)
#绘制路径代码略空间限制: 256MB
来源: 2022.10浙南名校第16题