目的達成可能性の必要十分条件

あなたの目的が達成できるための必要十分条件は，

• \(H \ge W + 2\)
• \(H = W + 1\) かつあなたが先に魔法を使う

のいずれかが成り立つことである．

十分性

まず，この条件が成り立つ場合に目的を達成できることを示す． ダンジョン外の左側領域に始点 \(s\) を，右側領域に終点 \(t\) を置き，ダンジョン内の各部屋を頂点とし，扉で隣接する部屋（または始点，終点）同士を辺で結んで得られるグラフ \(G\) を考える． あなたの目的は，自分の選んだ辺だけで \(s\) と \(t\) を連結にすることである． さらに言い換えれば，あなたは辺を縮約して両端点を \(1\) つにマージすることができ，大魔王 DEGwer は辺を削除できると見なしたときに，最終的に \(s\) と \(t\) を同じ頂点にマージできることが必要十分である．

ここで，\(G\) 中に辺素な \(2\) つの全域木 \(T_1, T_2\) を取れたとする． このとき，あなたの目的が達成可能であることが，以下のように帰納的に証明できる．

• 大魔王 DEGwer が選んだ辺が \(T_1, T_2\) のどちらにも存在しない場合，あなたが残りのどの辺を選んだとしても，縮約後のグラフ中に辺素な \(2\) つの全域木が取れる状況は変わらない．

• 大魔王 DEGwer が選んだ辺が \(T_1, T_2\) のどちらかに存在する場合，その辺を削除することで一方の全域木は \(2\) つの連結成分に分かれてしまうが，他方の全域木にはそれらの連結成分を跨ぐ辺が必ず存在する． あなたはそのような辺を選ぶことで，縮約後のグラフ中に辺素な \(2\) つの全域木が取れる状況を保つことができる．

\(G\) は非常に特殊で対称的な形をしているので，\(H \ge W + 2\) の場合に具体的に辺素な全域木を構成することは難しくない． \(H = W + 1\) かつあなたが先に魔法を使う場合は，\(s, t\) 間に仮想的な辺を追加するとやはり辺素な全域木を具体的に構成でき，追加した仮想辺を大魔王 DEGwer に先に削除されたと考えれば，同じ方法で目的を達成することができる．

必要性

大魔王 DEGwer の立場に立って考えると，双対に近いグラフで同じ目的を達成しようとしていることになる． 具体的には，先ほど構成したグラフ \(G\) について，\(s\) から左に伸びる半直線と \(t\) から右に伸びる半直線で外領域を仮想的に二分し，その双対グラフ \(\tilde{G}\) を考える．（ \(2\) 本の半直線は辺として扱わない．） すると，大魔王 DEGwer の目的は，\(2\) つの外領域に対応する \(H\) の頂点を \(\tilde{s}, \tilde{t}\) として，自分の選んだ辺だけで \(\tilde{s}\) と \(\tilde{t}\) を連結にすることであると言い換えられる．

この \(\tilde{G}\) は，元のダンジョンから作られるグラフ \(G\) を \(90^\circ\) 回転して少し横に伸ばしたような形をしており，厳密には \((W + 1)\) 行 \((H - 1)\) 列のダンジョンから作られるグラフ \(G\) と同型である． したがって，\(H \le W\) の場合の \(\tilde{G}\) であれば \(W + 1 \ge (H - 1) + 2\) が成り立つため目的が達成可能であり，\(H = W + 1\) の場合の \(\tilde{G}\) であれば \(W + 1 = (H - 1) + 1\) が成り立つため，自分が先に魔法を使えるなら目的が達成可能である．

まとめ

以上より，目的達成可能性の必要十分条件と，具体的な達成方法が示されたので，これを適切に実装すればよい． 本問の入力として現れるグラフは非常に限定的なので，それらについてあらかじめ辺素な全域木を見つけておけば，各反復では頂点数と辺数が \(\mathrm{O}(HW)\) のグラフの連結成分の計算と削除・縮約辺の処理をするだけでよく，反復回数が \(\mathrm{O}(HW)\) 回であるため，全体の計算時間は \(\mathrm{O}(H^2W^2)\) である．

補足

このような辺の縮約と削除を交互に行って \(2\) 頂点をマージできるかどうかを競うゲームは Shannon switching game と呼ばれ，一般のグラフにおいてもマトロイド交叉を用いて多項式時間で解けることが知られている． 大魔王 DEGwer はもちろんマトロイド交叉を知っているため，自分が勝てる状況になれば必ず勝つようなインタラクタが実装されている． ただし，こちらの計算量は \(\Theta(H^3W^3)\) であり，本問題の想定解（グラフの特殊性を利用して辺素な全域木をあらかじめ求めておく）よりは重くなっている．