def question4(string_maze): # 幅優先探索を使って迷路を探索する
    maze = arrayize_maze(string_maze) # 文字列型の迷路を２次元配列型に変換する
    moves = [(0, -1), (0, 1), (-1, 0), (1, 0)] # 順番に、上、下、左、右
    X = len(maze[0]) # 迷路の横の長さを測る
    Y = len(maze) # 迷路の縦の長さを測る
    distmtx = [] # 距離行列：スタートからの最短距離（歩数）を格納する

    # 距離行列の初期値として、ありえない大きな値を入れておく
    for y in range(Y):
        distmtx.append([X * Y for x in range(X)])

    # 迷路のスタートとゴールの x座標、y座標を見つける
    sx, sy, gx, gy = find_start_goal(maze)

    queue = [] # 待ち行列
    queue.append([sx, sy]) # 待ち行列にスタート座標を入れる
    distmtx[sy][sx] = 0 # スタート座標の「距離」をゼロにする

    while len(queue) > 0:
        curr = queue.pop(0) # 現在位置を取得（深さ優先的に）
        if curr[0] == gx and curr[1] == gy: # もしもゴールの座標と同一なら
            #print(distmtx)
            return distmtx[curr[1]][curr[0]] # スタートからゴールの距離を返す
        for dx, dy in moves: # 次の一歩（上下左右）
            new_x = curr[0] + dx # 次のx座標
            new_y = curr[1] + dy # 次のy座標

            # 迷路の外ではなくて（x座標）
            # 迷路の外ではなくて（y座標）
            # 壁ではなくて
            # 未訪問の場合
            if (new_x >= 0) and (new_x < X) \
                    and (new_y >= 0) and (new_y < Y) \
                    and (maze[new_y][new_x] != "#") \
                    and (distmtx[new_y][new_x] == X * Y):
                queue.append([new_x, new_y]) # 次の座標を queue に入れる
                # 次の座標の距離行列の値＝現在位置の距離＋１
                distmtx[new_y][new_x] = distmtx[curr[1]][curr[0]] + 1
    return False # もし辿り着けなかったら False

def arrayize_maze(string_maze): # 文字データの迷路を配列データに変換する
    return [[str[i] for i in range(len(str))] for str in string_maze.split()]

def find_start_goal(maze): # 迷路のスタートとゴールの座標を同定する
    sx = 0
    sy = 0
    gx = 0
    gy = 0
    for y in range(len(maze)):
        for x in range(len(maze[y])):
            if maze[y][x] == 'S':
                sx = x
                sy = y
            elif maze[y][x] == 'G':
                gx = x
                gy = y
    return (sx, sy, gx, gy)

string_maze = \
    '__##_S______\n' \
    '##_##____##_\n' \
    '______#_____\n' \
    '#_#_#______#\n' \
    '__#______#_#\n' \
    '#______#___#\n' \
    '_#_##______#\n' \
    '___###__#__G\n' \
    '_###_____##_\n' \
    '_#__#_______\n'

question4(string_maze)

13

string_maze = \
    '__S#__#___##\n' \
    '_____#___###\n' \
    '__##__#__###\n' \
    '_#__##___#_#\n' \
    '_###_##____#\n' \
    '_____#_###__\n' \
    '________#_#_\n' \
    '#______#_#_#\n' \
    '#___#___#___\n' \
    '________#G__\n' 

question4(string_maze)

False

string_maze = \
    'S_#_##__###_\n' \
    '#___#__#__##\n' \
    '_##_______#_\n' \
    '___##__#_##_\n' \
    '___#__#_#___\n' \
    '#____#____#_\n' \
    '__#_##G####_\n' \
    '_____##___#_\n' \
    '____##__#___\n' \
    '#_#____##_#_\n' \

question4(string_maze)

38

string_maze = \
    '##___###_#_#\n' \
    '#___S###_#_#\n' \
    '##_#________\n' \
    '___#__##_#__\n' \
    '____##______\n' \
    '_#____#__##_\n' \
    '#___#_#____#\n' \
    '___________#\n' \
    '_#__#____#_#\n' \
    '#____#___###\n' \
    '__#_#_#_#___\n' \
    '#__##_#_#_#G\n' \
    '#__##_____##\n' \
    '#__#____#___\n' \
    '#__#_#__##_#\n' \

question4(string_maze)

23