廣度優先搜索錯誤輸出

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.