ABC151-D_MazeMasterをpythonで解いた（BFS）

問題

• ABC151-D_MazeMaster

ポイント

• 迷路の最短経路問題
• -> BFS
• -> AtcorderABC-Dより先へ行くために代表的なアルゴリズムを勉強した-その3-（DFS、BFS）.md
• -> 上記は、スタートとゴールが決まっている版。今回は、『ゴール決めずに全部調べる+距離の最大値を持っておいて適宜更新する』、という処理を加える

解法

def C_BFS(R, C, sy, sx, gy, gx, c):
    """
    R:行数
    C:列数
    sy,sx:スタートの座標(sy行sx列)
    gy,gx:ゴールの座標(gy行gx列)
    c:迷路の形状(.:通路,#:壁)
    """
    INF = float('inf')
    sy -= 1
    sx -= 1
    gy -= 1
    gx -= 1

    def bfs(maze, row, column, sy, sx, gy, gx):
        # 原点は(0,0)とする(問題の制約によっては原点をずらす必要がある)
        queue = []
        queue.insert(0, (sy, sx))
        dist = [[INF for _ in range(column)] for _ in range(row)]
        dist[sy][sx] = 0  # yが行数、xが列数を意味するときはこの順に書く
        # （追記）距離の最大値を持っておく
        dist_max = 0
        while len(queue):
            y, x = queue.pop()
#             if x == gx and y == gy:
#                 # ゴール座標と一致するなら
#                 break
            for i in range(4):
                nx, ny = x + [1, 0, -1, 0][i], y + \
                    [0, 1, 0, -1][i]  # (x,y)の右、上、左、下
                if 0 <= nx and nx < column and 0 <= ny and ny < row \
                        and maze[ny][nx] != '#' and dist[ny][nx] == INF:
                    #(nx,ny)が迷路内であり、壁でなく、まだ距離が確定していないとき
                    queue.insert(0, (ny, nx))  # 次に探索する座標
                    dist[ny][nx] = dist[y][x] + 1
                    # （追記）距離の最大値を更新する
                    if dist_max < dist[ny][nx]:
                        dist_max = dist[ny][nx]
        return dist_max
#         return dist[gy][gx]

    maze = [['' for _ in range(C)] for _ in range(R)]
    for i, tmp in enumerate(c):
        for j in range(C):
            maze[i][j] = tmp[j]

    ans = bfs(maze, R, C, sy, sx, gy, gx)
    return ans

R , C = [int(i) for i in input().split()]
c = [input() for _ in range(R)]

# スタート地点は全て試す
dist_ans = 0
for sy in range(1, R+1):
    for sx in range(1, C+1):
        if c[sy-1][sx-1] != '#':
            dist_tmp = C_BFS(R, C, sy, sx, 1, 1, c) # 今回、 gy, gx は不要
            if dist_ans < dist_tmp:
                dist_ans = dist_tmp
print(dist_ans)

感想

• BFSの典型的な問題？