問題
二次元フィールドが与えられる。フィールドのいくつかのセルには障害物がある。
障害物の無い各セルを初期値として、次のターン制2人ゲームを行う。
現在地から4方向に1セル移動する。ただし、障害物があるか一度踏んだセルは侵入できない。行動できなくなったプレーヤーが負け。
各セルについて、そのセルを初期値としたとき先手必勝か後手必勝か答えよ。
解法
まず2部グラフの最大マッチングを求める。
マッチ相手に移動する戦略が強い。
初期値がマッチしていないセルに来た場合、後手必勝である。
初期値から移動した先のセルはマッチ相手が居る。後攻はそのマッチ相手に移動すればよい。なぜなら、もし先手が移動した時にマッチ相手のいないセルなら、そこまでのパスはaugment pathになり、マッチ相手をひっくり返すとマッチングが増えるからである。
初期値がマッチ相手を持つ場合、先手はマッチ相手に移動するのがよい。
後手にマッチ相手のいない頂点に移動されると負けるが、そのような頂点があるときに、初手でマッチ相手とは違う頂点に移動しても別のマッチ相手のいない頂点に移動することはできない。
後手の移動の選択は任意だが、パスを記憶する必要はなく、同じ頂点を繰り返し計算しない。
