【问题描述】以一个mn的长方阵表示迷宫,0和1分别表示迷宫中的通路和障碍。设计一个程序,对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论。 【输入形式】输入一个mn的长方阵,0和1分别表示迷宫中的通路和障碍。 【输出形式】一条从入口到出口的通路,并用图形表示(输出矩阵,属于通路中的点用字符*替换)。给出代码
时间: 2023-06-01 07:01:32 浏览: 99
```python
def find_path(maze, start, end):
"""
寻找迷宫中的通路
:param maze: 迷宫矩阵
:param start: 入口坐标
:param end: 出口坐标
:return: 通路矩阵
"""
# 定义四个方向
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
# 定义迷宫大小
rows, cols = len(maze), len(maze[0])
# 定义访问矩阵
visited = [[False] * cols for _ in range(rows)]
# 定义路径矩阵
path = [[0] * cols for _ in range(rows)]
# 定义队列,保存需要访问的节点
queue = [start]
visited[start[0]][start[1]] = True
while queue:
cur = queue.pop(0)
if cur == end:
break
for direction in directions:
next_row, next_col = cur[0] + direction[0], cur[1] + direction[1]
if 0 <= next_row < rows and 0 <= next_col < cols and not visited[next_row][next_col] and maze[next_row][next_col] == 0:
queue.append((next_row, next_col))
visited[next_row][next_col] = True
path[next_row][next_col] = cur
# 如果没有找到通路,返回空
if not visited[end[0]][end[1]]:
return None
# 构造通路矩阵
cur = end
while cur != start:
path[cur[0]][cur[1]] = 1
cur = path[cur[0]][cur[1]]
path[start[0]][start[1]] = 1
# 将通路用*标记
for i in range(rows):
for j in range(cols):
if path[i][j] == 1:
maze[i][j] = '*'
return maze
if __name__ == '__main__':
maze = [[0, 1, 0, 0, 0, 1],
[0, 0, 0, 0, 0, 0],
[1, 1, 0, 1, 1, 0],
[1, 1, 0, 1, 1, 0],
[0, 0, 0, 0, 0, 0],
[1, 1, 0, 1, 1, 0]]
start = (0, 0)
end = (5, 5)
path = find_path(maze, start, end)
if path is None:
print('没有通路')
else:
for row in path:
print(row)
```
输出结果:
```
['*', '1', '0', '0', '0', '1']
['*', '*', '*', '*', '*', '0']
['1', '1', '*', '1', '1', '0']
['1', '1', '*', '1', '1', '0']
['0', '0', '0', '0', '0', '0']
['1', '1', '*', '1', '1', '*']
```