使用A*算法求解迷宫问题_a*算法迷宫例题

本题目要求读入一个5*5的迷宫，然后输出基于A*算法求解的从左上角（0,0）到右下角（4,4）的路径。

输入格式:

迷宫是一个5*5的二维数组，其中0代表可以通过，1代表墙壁不能通过。

迷宫的左上角和右下角必须是0

读入迷宫语句参考如下：

str = input("")
 
maze = eval(str)
'
运行
运行

输出格式:

以列表形式表示的一条通路，列表中的每个元素为一个元组(x,y)，x和y分别表示横纵坐标。

输入样例:

例如：

[[0,0,1,0,0],[0,0,0,0,0],[0,0,0,0,1],[1,0,1,0,1],[0,0,1,0,0]]

输出样例:

在这里给出相应的输出。例如：

[(0, 0), (0, 1), (1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (4, 3), (4, 4)]

 示例：

import heapq
def astar(maze):
    start = (0, 0)
    end = (4, 4)
    queue = []
    heapq.heappush(queue, (0, start))
    parent = {}
    g_score = {start: 0}
    f_score = {start: heuristic(start, end)}
    
    while queue:
        _, current = heapq.heappop(queue)
        
        if current == end:
            path = []
            while current in parent:
                path.append(current)
                current = parent[current]
            path.append(start)
            path.reverse()
            return path
        
        for neighbor in get_neighbors(current, maze):
            if neighbor in g_score and g_score[current] + 1 >= g_score[neighbor]:
                continue
 
            parent[neighbor] = current
            g_score[neighbor] = g_score[current] + 1
            f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, end)
            heapq.heappush(queue, (f_score[neighbor], neighbor))
    return None
def heuristic(node, end):
    return abs(node[0] - end[0]) + abs(node[1] - end[1])
def get_neighbors(node, maze):
    neighbors = []
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    for direction in directions:
        x = node[0] + direction[0]
        y = node[1] + direction[1]
        
        if 0 <= x < len(maze) and 0 <= y < len(maze[0]) and maze[x][y] == 0:
            neighbors.append((x, y))
    return neighbors
str = input("")
maze = eval(str)
path = astar(maze)
 
print(path)