DFS遍歴n*mの地図

1.図

.#.........
.#.#######.
.#.#.....#.
.#.#.###.#.
.#.#..@#.#.
.#.#####.#.
.#.......#.
.#########.
...........

出発点を表す.歩くことができることを表して、'#'は障害を表して、この図に対して遍歴して、そして歩く歩数を統計します
2.アルゴリズムの原理
図を変更すると、アクセスの準備をするノードを1つのキューで保存することができ、最初に開始点をキューに入れ、ヘッダノードにアクセスし、アクセスするときに、その上下左右のノードを探索し、未アクセスを満たし、キューに入れず、ノードは'.これをキューに入れ、アクセスが終了するとノードをマークし、そのノードをキューから削除して、ペアが空になるまでペアのヘッダノードにアクセスします.
3.コード実装(python)

# f = lambda:map(int, input().split())
# n, m = f()
#
# g = [''] * n
#
# for i in range(n):
#     g[i] = input()

n = 9
m = 11
v = [[0] * m for i in range(n)]
g = ['.#.........',
     '.#.#######.',
     '.#.#.....#.',
     '.#.#.###.#.',
     '.#.#..@#.#.',
     '.#.#####.#.',
     '.#.......#.',
     '.#########.',
     '...........']

#     
si, sj = 0, 0
for i in range(n):
    for j in range(m):
        if g[i][j] == '@':
            si = i
            sj = j
print(si, sj)

#       
l = []


def bfs(i, j):
    c = 0
    # Q   
    Q = [(i, j)]
    while Q:
        c += 1
        i, j = Q[0]
        l.append((i, j))
        # print(g[i][j])
        #            ，    、        Q 、    '.'    ，  Q 
        if 0 < j and not v[i][j-1] and (i, j-1) not in Q and g[i][j-1] == '.':
            Q.append((i, j-1))
        if j < m-1 and not v[i][j+1] and (i, j+1) not in Q and g[i][j+1] == '.':
            Q.append((i, j+1))
        if 0 < i and not v[i-1][j] and (i-1, j) not in Q and g[i-1][j] == '.':
            Q.append((i-1, j))
        if i < n-1 and not v[i+1][j] and (i+1, j) not in Q and g[i+1][j] == '.':
            Q.append((i+1, j))
        # mark (i, j)
        v[i][j] = 1
        #          Q   
        Q.remove((i, j))
    return c


#      dfs
print(bfs(si, sj))

print(l)

4.結果出力

    ：
4 6
59
      ：
[(4, 6), (4, 5), (4, 4), (3, 4), (2, 4), (2, 5), (2, 6), (2, 7), (2, 8), (3, 8), (4, 8), (5, 8), (6, 8), (6, 7), (6, 6), (6, 5), (6, 4), (6, 3), (6, 2), (5, 2), (4, 2), (3, 2), (2, 2), (1, 2), (0, 2), (0, 3), (0, 4), (0, 5), (0, 6), (0, 7), (0, 8), (0, 9), (0, 10), (1, 10), (2, 10), (3, 10), (4, 10), (5, 10), (6, 10), (7, 10), (8, 10), (8, 9), (8, 8), (8, 7), (8, 6), (8, 5), (8, 4), (8, 3), (8, 2), (8, 1), (8, 0), (7, 0), (6, 0), (5, 0), (4, 0), (3, 0), (2, 0), (1, 0), (0, 0)]