考察
視線に入るかを先に確定できれば、残る問題は各辺コスト1の grid 最短路なので BFS である。視線は壁または人で止まり、S/G や空きマスでは止まらない。人ごとに長い ray を独立に伸ばす代わりに、各行・各列を四方向から一度ずつ読む。最後に見たblockerの種類だけを持てば各マスを定数回で処理できる。左から右のscanでは最後のblockerが右向き人なら、その後の空きマスは監視下にある。壁または別の人に会った時点で状態を更新し、残り三方向も同様に処理する。監視マスは通れないが視線を遮らない。視線を止めるのは # と四種の人だけなので、mark済み空きマスでscanを止めてはいけない。
採用する候補: 行列の四方向scanで監視マスを印付け、そのマスと障害物・人を通行不可にして S から BFS する。
前処理と探索がともに O(HW) で、視線計算と最短路計算の責務を分離できる。
棄却する候補: BFS 中に各候補マスから四方向を逆走し、見張る人がいるか都度調べる。
開けた行列では一移動判定に O(H+W) かかり、全体が O(HW(H+W)) まで悪化する。
監視マスは通れないが視線を遮らない。
viewed を false で作り、各行を左右から、各列を上下から走査する。対応方向を向く人の後で blocker までの . を viewed=true にする。次に #・人・viewed を禁止として S から四近傍 BFS し、G の距離または −1 を出す。
典型の発動条件
ray制約の四方向scan
発動条件: grid 上の直線効果が blocker まで続き、方向種類が定数個のとき。
各行・各列を一方向にscanし、現在activeなrayの有無だけを持って全マスを一度ずつ印付ける。
制約前処理+BFS
発動条件: 移動不能条件が位置だけで決まり、移動ごとに再計算する必要がないとき。
危険マスを静的 obstacle に変換して単位重み最短路を解く。
問題固有の要素
監視されたことと視線を遮ることは別属性であり、前者をobstacleとしてBFSに使っても方向別scanのblockerにはしない。
別の問題へ持ち帰る視点: grid 前処理では「入れない」「効果を止める」を同じ boolean に潰さず、意味ごとに分ける。
正当性
各rayは壁か人でだけ止まるので走査方向に最後のblockerを覚えると全viewedセルが厳密に決まる。危険セルを通行不可にした残存graphは元の合法移動と一致し単位辺BFSで最短。S/Gも視線遮断物として扱わず公式セル条件を守る。
実装上の注意
- S/Gは監視外保証だが方向別scanでは空きマス同様に視線を通す。人のマス自身はviewedにせずとも常にBFS禁止とする。
復習の核
- 前処理の blocker 条件と BFS の通行条件を別に列挙する。四方向実装は方向配列で共通化し、端・連続する人をテストする。
計算量と制約
時間
H×W。四方向視線走査とBFS O(HW)。
空間
盤面、視線flag、dist O(HW)。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 2 \leq H, W \leq 2000; A_{i,j} is ., #, >, v, <, ^, S, or G.; Each of S and G occurs exactly once among A_{i, j}.; Neither the starting point nor the goal is in a person's line of sight.
出典