meiro.py

# 迷路の最短路
# 蟻本　p.37

N = 10
M = 10

meiro = """\
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
"""

meiro = [list(m) for m in meiro.split('\n')]
d = [[0] * M for i in range(N)]

def bfs(start):
    position = [start]

    while True:
        x, y = position.pop(0)

        if meiro[x][y] == "G":
            return d[x][y]

        meiro[x][y] = 'X'

        for dx, dy in [(-1, 0), (0, -1), (1, 0), (0, 1)]:
            nx = x + dx
            ny = y + dy
            if 0 <= nx < N and 0 <= ny < M:
                if meiro[nx][ny] in ('.', 'G'):
                    position.append((nx, ny))
                    d[nx][ny] = d[x][y] + 1

def solve():
    for i in range(N):
        for j in range(M):
            if meiro[i][j] == "S":
                start = (i, j)

    return bfs(start)
    
print(solve())