[Python] ABC020 C 全探索 40点

問題

C – 壁抜け

回答

スライドの方針に従って、深さ優先探索により全ての経路を探索し、最初にゴールに到達できた x を解答にします。

AtCoder Beginner Contest 020 解説 from AtCoder Inc.

H, W, T = map(int, input().split())
s = [input() for _ in range(H)]

for h in range(H):
    for w in range(W):
        if s[h][w] == 'S':
            start = (h, w)

move = ((-1, 0), (0, -1), (1, 0), (0, 1))

def dfs(now, x, t, ts):
    # now:現在の位置 x:黒ますの移動時間 t:現在の経過時間 ts:ゴールに到着できた時間
    for h_move, w_move in move:
        next_pos = (now[0] + h_move, now[1] + w_move)
        # 移動先がマス内
        if (0 <= next_pos[0] < H) and (0 <= next_pos[1] < W):
            # 移動先がゴールで制限時間内に到着できる
            if s[next_pos[0]][next_pos[1]] == 'G' and t+1 <= T:
                ts.append(t + 1) 
                continue

            if s[next_pos[0]][next_pos[1]] == '.' \
                or s[next_pos[0]][next_pos[1]] == 'S':
                if t+1 <= T:
                    dfs(next_pos, x, t+1, ts)
            else:
                if t+x <= T:
                    dfs(next_pos, x, t+x, ts)
    return ts
    

for x in range(T-1, 0, -1):
    t = 0
    ts = []
    ts = dfs(start, x, t, ts)
    if ts:
        print(x)
        break