Game Play

Basics

由两位玩家进行对战，并且游戏规则对于每位玩家都是相同的。通常情况下，题目会给你一定的前提条件，所要做的就是判断出谁最后会赢。

我所遇到的题目，基本都是用 recursion 来做。

recursion(parameter 1, parameter 2, ..., int player)

与一般的 recursion 不同的是，这类 recursion tree 是交替的，即

                                p1
                          p2
                    p1
             p2

终止条件是，无路可走。

经典题目

294 Flip Game II

class Solution {
    public boolean canWin(String s) {
        char[] array = s.toCharArray();
        // 0: player 1
        // 1: player 2
        return canWin(array, 0);
    }
    
    // Player 1 and Player 2 have the same right.
    // If P1 made a move, and then found that P2 couldn't make a move (false), then P1 won (true).
    // Same to P2.
    // The only difference would be who is the first player to move.
    private boolean canWin(char[] array, int player) {
        for (int i = 0; i < array.length - 1; i++) {
            if (array[i] == '+' && array[i + 1] == '+') {
                array[i] = '-';
                array[i + 1] = '-';
                boolean flag = canWin(array, 1 - player);
                array[i] = '+';
                array[i + 1] = '+';
                if (!flag) return true;
            }
        }
        return false;
    }
}