meiro.py

#  迷路の経路を出力
import copy

N = 10
M = 10

meiro = """\
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#
"""
print("Map")
print(meiro)

meiro = [list(m) for m in meiro.split('\n')]
meiro_org = copy.deepcopy(meiro)


def bfs():
    queue = []
    start = (0, 1)
    goal = (9, 8)
    queue.append([start])

    while True:
        path = queue.pop(0)
        x, y = path[-1]
        if (x, y) == goal:
            return path
        for nx, ny in ((x-1, y), (x+1, y), (x, y-1), (x, y+1)):
            if 0 <= nx < N and 0 <= ny < M and meiro[nx][ny] != '#':
                meiro[nx][ny] = '#'
                newpath = path.copy()
                newpath.append((nx, ny))
                queue.append(newpath)


path = bfs()
for x, y in path:
    meiro_org[x][y] = '*'

print("Result")
print("\n".join(["".join(line) for line in meiro_org]))

output.txt

Map
#S######.#
......#..#
.#.##.##.#
.#........
##.##.####
....#....#
.#######.#
....#.....
.####.###.
....#...G#

Result
#*######.#
.**...#..#
.#*##.##.#
.#****....
##.##*####
....#****#
.#######*#
....#****.
.####*###.
....#****#