Game (UVa Live Archive Europe - Southeastern - 2010/2011 Bucharest (Romania))

http://acmicpc-live-archive.uva.es/nuevoportal/data/problem.php?p=4823

問題

n*nの行列上で二人でゲームをする。各プレイヤーは自分の手番で行列の一番右の列か一番下の行の総和が偶数の場合にその列を消すことができる。列を消せなくなったプレイヤーが負けとなる。先手が勝つかどうか求めよ。
n<=1000

解法

ゲーム木探索。