読者です 読者をやめる 読者になる 読者になる

AtCoder AGC 014 C: Closed Rooms

k回目の魔法で部屋を開いた状態にする操作は、k+1回目以降の移動にしか影響しない。

よって、魔法を以下のように捉え直す。

1回目の魔法は移動のみ

2回目の魔法は部屋を開く操作ののち、移動

2回目以降の操作はK個以下の部屋を開き、K個以下のマスを移動できるので、出口へまっすぐ進めばいい。よって1回目の移動でどのマスへ行けるかを探索で調べる。到達できた各マスについて、到達可能なマス(x, y)から外へ通じるマスまでの距離をd(x, y) とした時

min(ceil(d(x, y)/K)+1)

が解。