洛谷p1238+走迷宫链表
时间: 2023-12-21 14:31:17 浏览: 33
洛谷p1238是一个题目,具体要求是给定一个迷宫,求从起点到终点的最短路径。这个问题可以使用链表来表示迷宫,并使用广度优先搜索算法来求解最短路径。
以下是一个示例代码,演示了如何使用链表和广度优先搜索算法来解决洛谷p1238题目中的迷宫问题:
```python
from collections import deque
# 定义迷宫的链表节点类
class Node:
def __init__(self, x, y, val):
self.x = x
self.y = y
self.val = val
self.next = None
# 构建迷宫的链表
def build_maze(maze):
m = len(maze)
n = len(maze[0])
head = Node(0, 0, maze[0][0])
curr = head
for i in range(m):
for j in range(n):
if i == 0 and j == 0:
continue
node = Node(i, j, maze[i][j])
curr.next = node
curr = node
return head
# 广度优先搜索算法求解最短路径
def bfs(maze):
m = len(maze)
n = len(maze[0])
visited = [[False] * n for _ in range(m)]
queue = deque([(0, 0, 0)]) # (x, y, step)
visited[0][0] = True
while queue:
x, y, step = queue.popleft()
if x == m - 1 and y == n - 1:
return step
for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and not visited[nx][ny] and maze[nx][ny] == 0:
queue.append((nx, ny, step + 1))
visited[nx][ny] = True
return -1
# 示例迷宫
maze = [
[0, 1, 0, 0, 0],
[0, 1, 0, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 1, 1, 0],
[0, 0, 0, 1, 0]
]
# 构建迷宫的链表
maze_head = build_maze(maze)
# 使用广度优先搜索算法求解最短路径
shortest_path = bfs(maze)
print("最短路径长度为:", shortest_path)
```