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)
が解。