广度搜索解决布线问题的python代码

以下是使用广度优先搜索（BFS）算法解决布线问题的Python代码：

from queue import Queue

# 定义节点类
class Node:
    def __init__(self, x, y, cost, path):
        self.x = x # 节点的x坐标
        self.y = y # 节点的y坐标
        self.cost = cost # 到达该节点的代价
        self.path = path # 到达该节点的路径

# 定义布线问题解决函数
def solve(start, end, obstacles):
    # 定义移动方向
    dx = [0, 0, 1, -1]
    dy = [1, -1, 0, 0]
    # 初始化起点和终点节点
    start_node = Node(start[0], start[1], 0, [])
    end_node = Node(end[0], end[1], 0, [])
    # 初始化队列
    queue = Queue()
    queue.put(start_node)
    # 初始化已访问节点集合
    visited = set()
    visited.add((start_node.x, start_node.y))
    # 广度优先搜索
    while not queue.empty():
        # 取出队首节点
        cur_node = queue.get()
        # 如果当前节点为终点，返回路径
        if cur_node.x == end_node.x and cur_node.y == end_node.y:
            return cur_node.path + [(cur_node.x, cur_node.y)]
        # 遍历四个方向
        for i in range(4):
            nx = cur_node.x + dx[i]
            ny = cur_node.y + dy[i]
            # 如果新节点在障碍物范围内或者已经访问过，跳过
            if (nx, ny) in obstacles or (nx, ny) in visited:
                continue
            # 添加新节点到队列中
            new_node = Node(nx, ny, cur_node.cost+1, cur_node.path+[(cur_node.x, cur_node.y)])
            queue.put(new_node)
            visited.add((nx, ny))
    # 如果无法到达终点，返回空路径
    return []

# 测试
start = (0, 0)
end = (5, 7)
obstacles = {(2, 2), (3, 2), (4, 2), (4, 3), (4, 4), (3, 4)}
path = solve(start, end, obstacles)
print(path)

该代码使用了队列来实现广度优先搜索，每次取出队首节点进行扩展，并将扩展出的新节点加入队列中。为了避免重复访问，使用了一个集合来记录已经访问过的节点。在遍历四个方向时，需要注意判断新节点是否在障碍物范围内或者已经访问过。如果搜索到终点节点，返回路径，否则返回空路径。