AOJ 0236 （Alien Messages : 宇宙人のメッセージ）
【問題】
https://onlinejudge.u-aizu.ac.jp/problems/0236
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0236
【解説】
各マス目のハミルトン閉路が存在するかを判定する問題。上記を満たす場合、必ず全空きマスに入る辺と出る辺が1対ずつ存在することになる。
そのため、以下の6パターンのピースをセットできるかを全空きマスに対し、バックトラック法にて探索していけばよい。
セット可能かについては、セットするマスの周囲を確認し、
- ピースの接続する辺が壁や石像と接していないこと
- ピースの接続しない辺が設置済ピースの接続する辺と接していないこと
の2条件を満たせば、配置可能として探索を進めていく。全探索のケースは"6^空マスの数"と膨大だが、上記条件で順次バックトラック法を行っていけば、設置可能なケースはそこまで多くないため、現実的な時間で求めることが十分可能である。
上記の条件で配置をしていくと、最後のピースを置き終わった時点では、全ての空きマスを使って、
- 単一の閉曲線1つが構築できている
- 複数の閉曲線が構築できている
のいずれかの状態となっている。よって、任意の空きマスであった場所から線で接続されているマスをたどっていき、訪問したマスの数が全空きマスであった数と一致すれば、単一の閉曲線が構築できているため"Yes"を返す。（一致しなければ探索を継続する。）
なお、さらに処理時間を短縮するため、明らかにハミルトン閉路が構築できない以下のケースを探索前に"No"と判定している。
- 壁や石像に3辺以上囲まれている空きマスが存在する場合
- 空きマスの数が4つ未満の場合
- 空きマスの数が奇数の場合
まず、１のケースでは、要は行き止まりのマスがあることになるため、閉路を構築できない。また2のケースでは、最小の閉路を構築するためには最低でも4マス必要であり、構築不可である。
3のケースであるが、以下のようなチェスボードで考えてみるとわかりやすい。
始めに1ピースを置いたとすると、閉路は線の一方から始まり、もう一方で終わることになる。そのため、初めのピースがどのような場合でも、閉路は必ず「黒」→…→「黒」の経路となり、奇数個のマスをたどることになるため、初めに置いた1ピースを加え、閉路がたどるマスの数は必ず偶数となる。よって、空きマスの数が奇数である場合は全てのマスを使用して閉路の構築は不可である。
【コード】
