ARC005 C - 器物損壊！高橋君

問題原文

atcoder.jp

解法

「２回まで壁を壊せる」→「壁に侵入するコストを１として、ゴールまでの最小コストが２以下なら２回までしか壁を壊してない」と言い換える。

辺のコストが０か１なので、01BFSが使える。

実装

from collections import deque
H, W = map(int, input().split())
G = [list(input()) for _ in range(H)]

sh, sw = -1, -1
gh, gw = -1, -1
for h in range(H):
    for w in range(W):
        if G[h][w] == 's':
            sh, sw = h, w
        if G[h][w] == 'g':
            gh, gw = h, w


dist = [[float('inf')] * W for _ in range(H)]
dist[sh][sw] = 0
que = deque([[sh, sw]])

while que:
    nh, nw = que.pop()
    for dh, dw in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
        nx_h, nx_w = nh + dh, nw + dw
        if not ((0 <= nx_h < H) and (0 <= nx_w < W)):
            continue

        if dist[nx_h][nx_w] != float('inf'):
            continue

        if G[nx_h][nx_w] == '#':
            dist[nx_h][nx_w] = dist[nh][nw] + 1
            que.appendleft([nx_h, nx_w])
        else:
            dist[nx_h][nx_w] = dist[nh][nw]
            que.append([nx_h, nx_w])

print('YES' if dist[gh][gw] <= 2 else 'NO')

感想

まぁこれはさくさく。