广度优先搜索错误输出

Question

teren = [ 
    '########', 
    '#s.....#', 
    '###..#.#', 
    '#...##.#', 
    '#.#....#', 
    '#.####.#', 
    '#......#', 
    '###e####' 
    ] 

def bfs(teren, start, end): 
    queue = [] 
    visited = [] 
    queue.append([start]) 

    while queue: 
     path = queue.pop() 
     node = path[-1] 

     x = node[0] 
     y = node[1] 

     if node == end: 
      return path 
     if node in visited or teren[x][y] == "#": 
      continue 

     visited.append(node) 

     for adjacent in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]: 
      new_path = list(path) 
      new_path.append(adjacent) 
      queue.append(new_path) 

print(bfs(teren, (1,1), (7, 3))) 

这是我曾经尝试浏览这个迷宫式的东西的代码，这是输出我得到[(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (2, 6), (3, 6), (4, 6), (4, 5), (4, 4), (4, 3), (3, 3), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1), (6, 2), (6, 3), (7, 3)]同时这也是输出我需要[(1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (4, 1), (5, 1), (6, 1), (6, 2), (6, 3), (7, 3)]

看来，这是印花走出所有可行走的坐标，但我不知道如何解决这个问题，网上所有使用网格的例子都集中在绘制混淆实际bfs的网格上。

Answer 1

如果您将队列视为队列，您将获得输出结果。这意味着你不弹出最后一个元素了，但是你脱离第一：

取代：

path = queue.pop() 

有：

path, queue = queue[0], queue[1:] 

或：

path = queue.pop(0) 

不过deque-objects更适合这样的操作：

from collections import deque 

def bfs(teren, start, end): 
    queue = deque([]) 
    visited = [] 
    queue.append([start]) 

    while queue: 
     path = queue.popleft() 
     # ...etc.