| | | (H,W)=(3,2) の盤面、 --- --- S | | | T 「|」および「---」が扉(計13個) --- --- | | |
「シャノンのスイッチングゲーム」と呼ばれるゲームの一種である。
特にこのようなグリッド状に限定したものを指して、Galeのゲーム や Bridg-it とも呼ぶらしい。
各部屋と S,T を頂点、扉を辺と見なす。
あなたは辺を固定し、魔王は辺を削除して、S と T を連結にできればあなたの勝ちとなる。
ゲームの必勝法として、グラフから「辺疎な(辺を共有しない)全域木を2つ取る」ことができれば、
後攻であっても、必ず全ての頂点を連結にできる。
当然 S,T も連結にできるので、勝利する。
全域木A ①--②--③-|-④--⑤--⑥ 片方の全域木に属する辺が切られたときでも、 全域木B ,-------,,------, もう一方の全域木はまるごと残っている。 ① ② ③ ④ ⑤ ⑥ こっちの方で、分かれた成分同士を |`------'`-------' | 結ぶような辺(たとえば②-④)を選ぶことで `--------------------' 全域木A ①--(②④)--⑤--⑥ 縮約したグラフでは、辺を共有しない全域木が2つある状態を維持できる ③--' 全域木B ⑤--③--①--⑥--(②④)
これを繰り返すと、全ての頂点が1つになるまで縮約(=全体を連結に)できることが示せる。
ただし、全域木が2つ取れないからといって、必敗とは限らないので注意。
さて、問題のグラフで辺は H×(W+1)+(H−1)×W=2HW+H−W 本ある。
一方、頂点は HW+2 個で、2つの全域木に必要な辺数は 2HW+2 本である。
少なくとも、2HW+H−W≥2HW+2、つまり H≥W+2 であることが必要となる。
では、H≥W+2 なら構成できるのか?
以下のようにすると、必ず構成できる。
A B A B (H,W) = (5,3) -A- -B- -A- Aだけの扉(を辺と見立てたグラフ)も、 B A B A Bだけの扉も、全域木を構成する -B- -A- -B- S A B A B T -A- -B- -A- B A B A -B- -A- -B- A B A B
また、H=W+1 の時、辺が1本だけ足りないのだが、
A x B x A x B (H,W) = (4,3) -A- -B- -A- B o A x B x A Aは全域木となっているが、 o -B- -A- -B- x Bが1本だけ足りず、完全には繋がらず A o B o A x B o成分とx成分の2つに分かれている -A- -B- -A- B o A o B o A
先攻の場合、この2成分を初手で縮約する(たとえば左上の -A-
を選ぶ)ことで、必勝法に持ち込める。
よって、「H≥W+2」または「H=W+1 かつあなたの先攻」の場合、勝利できる。
では、他の場合は必ず敗北するのか?
結論から言うと敗北する。以下、それを示す。
魔王からしてみると、扉の連結点を頂点と見立て、 これを閉じた扉によって上から下まで繋げることができれば、阻止が成功したと言える。
___ S___ / / \ \ | | | | (H,W) = (3,3) o--o--o--o | | | | o--o--o--o | | | | \ \ / / ~~~ T ~~
魔王にとっての必勝法も、このグラフから2つの全域木が取れればよいということになる。
全域木の構築の仕方もあなたの場合と同様にでき、結局、「H≤W」または「H=W+1 かつ魔王の先攻」なら、 魔王の必勝ということになり、ちょうどあなたの場合を逆にした条件であることが分かる。
勝利可能で実際にゲームを行う場合、H,W が小さいので、愚直にUnion-Findなどで連結判定を毎回やってよい。
「2つの全域木」を取ろうとすると、H≥W+3 の時に辺があまりややこしいので、 木でなくなってもよいので上述のナナメ状に、辺を2つのグループA,Bに分ける。
相手がAに属する辺を削除してきたら、(既に固定済みの辺)+(未確定のAの辺)をUniteした後、