Maze（code festival 2014 上海 [D]）

概要

問題文 → ■
公式解説 → なさそう？
自分の提出 → ■

解法

解説が見つからなかったので書いておきます。最大流アルゴリズムで解けます。

1. 各マス目 $v$ に対してノード $v_{\text{in}}, v_{\text{out}}$ をつくり、$v_{\text{in}}$ から $v_{\text{out}}$ に向かって容量 $1$ の有向辺を張る。$v = S$ の場合のみ、容量を $2$ とする
2. 隣接するマス目 $v, w$ について，もし $v$ から $w$ への移動が $AS$ 間または $BS$ 間の最短経路に含まれるならば、$v_{\text{out}}$ から $w_{\text{in}}$ に向かって容量 $1$ の有向辺を張る
3. source node から $A_{\text{in}}$, $B_{\text{in}}$ に向かって容量 $1$ の有向辺を張る
4. $S_{\text{out}}$ から sink node に向かって容量 $1$ の有向辺を張る

同じマス目を $1$ 度までしか通らないようにするために、1. のような辺の張り方をしました。あとは、source から sink への最大流を作り、

• 流量が $1$ 以下ならば解なし
• 流量が $2$ ならばパス分解をとることで解が構築できる

となります。最大流量が $O(1)$ なので、計算量 $O(HW)$ で解けています。