ARC 005 C 器物損壊！高橋君

競技プログラミング

qiita.com

続き。

atcoder.jp

むずくてワロタ。

問題概要

壁'#', 平地'.', スタート's', ゴール'g' で構成されたH*Wのマス内で、スタートからゴールまで、壁を2回まで壊していいから、平地を通って行けるか。

考えたこと(間違い)

  • s から g までに到達する経路の中で、壁を壊した回数をマスに記録する
  • g に到達するまでに、壊した壁の数の最小 2 以下 なら OK のはず
  • '#' でも '.' でも行かなきゃいけないはず

こんな感じで考えてたんだけど、「あれ、実装できない...、同じところ通ってまう...、minで更新できない...」となって袋小路。諦め。

教えてgoogle先生。

解答

mmxsrup.hatenablog.com

カッケー！！！ 3 次元配列でBFSするのが正解だったのか...

個人的にすごく貪欲っぽい解法だったことに驚きを隠せなかった。

あと今回はpythonでも通りました！！！！(嬉しい)

from collections import deque


def main():
    h, w = [int(i) for i in input().split()]
    f = []
    for i in range(h):
        f.append(list(input()))

    sy, sx = 0, 0
    for i in range(h):
        for j in range(w):
            if f[i][j] == 's':
                sy, sx = i, j
            elif f[i][j] == 'g':
                gy, gx = i, j

    d = [[[False for k in range(3)] for j in range(w)] for i in range(h)]

    q = deque()
    # tuple[y][x][t] := f[y][x]までに何回壁を壊したか
    q.appendleft((sy, sx, 0))
    d[sy][sx][0] = True

    y, x = 0, 0
    # g に到達するまでに、壊した壁の数の最小 < 2 なら OK のはず
    # '#' でも '.' でも行かなきゃいけないはず
    while q:
        y, x, t = q.pop()
        if f[y][x] == 'g':
            break
        for dy, dx in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            # f[y+dy][x+dx] を k 回訪れた時で、場合分けする
            # f[y+dy][x+dx] に、t 回壁を壊した状態で訪れる場合を考える
            if 0 <= y+dy < h and 0 <= x+dx < w and not d[y+dy][x+dx][t]:
                if f[y+dy][x+dx] == '#':
                    # 2 で来てるからダメ
                    if t == 2:
                        #ダメ
                        continue
                    else:
                        d[y+dy][x+dx][t+1] = True
                        q.appendleft((y+dy, x+dx, t+1))
                else:
                    d[y+dy][x+dx][t] = d[y][x][t]
                    q.appendleft((y+dy, x+dx, t))


    print('YES' if any([d[gy][gx][i] for i in range(3)]) else 'NO')


if __name__ == '__main__':
    main()

結構感動してる。復習して、いつでも書けるようにしたいなぁ。めっちゃ楽しいし、いいな。