幅優先探索(BFS)は、色々なバリエーションでプログラミングコンテストで出題されます。
　ここではそのBFSをpython3で実装する方法を、「プログラミングコンテストチャレンジブック（第2版）」（通称：蟻本）での問題を参考に、紹介します。
　今回は、p37 「迷路の最短路」です。

from collections import deque 
INF = float('INF') #INFの宣言
#入力
maze = [ ['#','S','#','#','#','#','#','#','.','#'],    
         ['.','.','.','.','.','.','#','.','.','#'],    
         ['.','#','.','#','#','.','#','#','.','#'],    
         ['.','#','.','.','.','.','.','.','.','.'],    
         ['#','#','.','#','#','.','#','#','#','#'],    
         ['.','.','.','.','#','.','.','.','.','#'],    
         ['.','#','#','#','#','#','#','#','.','#'],    
         ['.','.','.','.','#','.','.','.','.','.'],    
         ['.','#','#','#','#','.','#','#','#','.'],    
         ['.','.','.','.','#','.','.','.','G','#'] ]
N, M = 10, 10
sx, sy = 0, 1 #Startの座標
gx, gy = 9, 8 #Goalの座標
d = [ [INF for n in range(N)] for m in range(M) ] #各地点までの最短距離の配列,INFで初期化
dx, dy  = [1, 0, -1, 0], [0, 1, 0, -1]  #移動4方向のベクトル

#(sx, sy)から(gx, gy)への最短距離を求める
#たどり着けないとINF
def bfs():
    mydeque = deque()
    mydeque.append([sx, sy]) #スタート地点をdequeに入れる
    d[sx][sy] = 0            #スタート地点の距離を0にする
    # dequeが空になるまでループ
    while mydeque:
        #dequeの先頭を取り出す
        x, y = mydeque.popleft()
        #取り出してきた状態がGoalなら探索をやめる
        if x == gx and y == gy:
            break
        #移動4方向をループ
        for i in range(4):
            #移動後の点を(nx, ny) とする
            nx, ny = x + dx[i], y + dy[i]
            #移動可能かの判定とすでに訪れたことがあるかの判定(d[nx][ny] !=  INF なら訪れたことがある)
            if 0 <= nx and nx < N and 0 <= ny and ny < M and maze[nx][ny] != '#' and d[nx][ny] ==  INF:
                #移動できるならdequeに入れ、その点の距離を(x,y)からの距離+1で確定する
                mydeque.append([nx, ny])
                d[nx][ny] = d[x][y] + 1
    return d[gx][gy]

if __name__ == '__main__':
    res = bfs()
    print(res)