二、算法分析

　　因为对弈双方对棋局的当前状态是明确的，所以可以判定当前状态胜负情况。
　　可建立如下一棵对策树。
　　初始状态为根结点，从某一结点出发所能到达的所有状态称为该结点的子结点，终局状态为叶结点。我们定义结点的值为：从此结点出发，若能必胜，则该结点值为1，否则为0。因此所有结点的值都是可以确定的，而对于每一个结点有两种情况：

　　1. 若该结点为叶结点，则它的值为0。
　　2. 若该结点非叶结点，则该结点的值定义如下：若它所有子结点的值都为1，则该结点的值为0；否则，该结点的值为1。
　　实现时，我们可以采用深度搜索，由叶结点的值一层层往上递推，直至得出根结点的值。若根结点值为1，则先手必胜，否则后手必胜。

三、注意点
　　存储棋盘时可以采用邻接表以提高效率。

四、小结
　　这是一道典型的博弈题，是现在流行的一种题型，从IOI2001出了两道此类的题就可见一斑。因此，我们要熟练掌握有关的算法，并灵活加以应用。