Latin America Regional (2012-11-11)
UVa 12530

50*50以下のグリッドが与えられる．
幾つかのセルは黒く塗りつぶされていて，他のセルは白い．
2人でゲームを行う．順番に行動する．行動できなくなったら負け．先手必勝か後手必勝かを判定する問題．
　前回黒く塗ったセルの上下左右の白いセルを1つ選び黒く塗る．
　最初はどの白いセルを選んで黒く塗っても良い．

各白いセルをノードと見なして，上下左右の白いセルに枝をはる．
そのようなグラフにおいて，完全マッチングが存在すれば後手必勝．
なぜなら，後手は，マッチングにそって動かせばいつでも動ける．
そうでなければ，先手必勝．最大マッチングに含まれない白いマスを最初に選んで，後は後手必勝の後手のように動けば良い．
二部グラフなので，完全マッチングが存在するかどうかは最大流などで求められる．