数组之井字棋先后移动之我真的不想学了

发布于 2020-06-25  758 次阅读


[et_pb_section admin_label="section"]
[et_pb_row admin_label="row"]
[et_pb_column type="4_4"]
[et_pb_text admin_label="Text"]

A 和 B 在一个 3 x 3 的网格上玩井字棋。
井字棋游戏的规则如下:
玩家轮流将棋子放在空方格 (" ") 上。
第一个玩家 A 总是用 "X" 作为棋子,而第二个玩家 B 总是用 "O" 作为棋子。
"X" 和 "O" 只能放在空方格中,而不能放在已经被占用的方格上。
只要有 3 个相同的(非空)棋子排成一条直线(行、列、对角线)时,游戏结束。
如果所有方块都放满棋子(不为空),游戏也会结束。
游戏结束后,棋子无法再进行任何移动。
给你一个数组 moves,其中每个元素是大小为 2 的另一个数组(元素分别对应网格的行和列),它按照 A 和 B 的行动顺序(先 A 后 B)记录了两人各自的棋子位置。
如果游戏存在获胜者(A 或 B),就返回该游戏的获胜者;如果游戏以平局结束,则返回 "Draw";如果仍会有行动(游戏未结束),则返回 "Pending"。
你可以假设 moves 都 有效(遵循井字棋规则),网格最初是空的,A 将先行动。
方法一:模拟
我们可以模拟数组 move 中的每一步落子。我们使用两个集合 A 和 B 存放每位玩家当前已经落子的位置,并用集合 wins 存放棋子排成一条直线的所有情况(排成一行或一列各有 3 种,排成对角线有 2 种,总计 8 种)。当某位玩家落子时,我们枚举 wins 中的每一种情况,并判断该玩家是否将棋子落在了这些位置。如果满足了其中一种情况,则该玩家获胜。
如果直到落子完毕仍然没有玩家获胜,那么根据数组 move 的长度返回平局 Draw 或游戏未结束 Pending。
示例 1:
输入:moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
输出:"A"
解释:"A" 获胜,他总是先走。
"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"
char * tictactoe(int** moves, int movesSize, int* movesColSize){
    // 将 moves 填入虚拟棋盘, a 为 -1 , b 为 1
    int s[3][3] = {0};
    for (int i = 0; i < movesSize; i++) {
        int x = moves[i][0], y = moves[i][1];
        if (i & 1) s[x][y]++;//按位与判断奇,偶数;第一个i为0,则第一步必将是0,e也就是执行s[x][y]--,即实现了b先走;
        else s[x][y]--;
    }
    // 对角线判断
    int sumD1 = s[0][0] + s[1][1] + s[2][2];
    int sumD2 = s[0][2] + s[1][1] + s[2][0];
    if (sumD1 ==  3 || sumD2 ==  3) return "B";
    if (sumD1 == -3 || sumD2 == -3) return "A";
    // 横向、纵向判断
    for (int i = 0; i < 3; i++) {
        int sumR = s[i][0] + s[i][1] + s[i][2];
        int sumC = s[0][i] + s[1][i] + s[2][i];
        if (sumR ==  3 || sumC ==  3) return "B";
        if (sumR == -3 || sumC == -3) return "A";
    }
    // 无胜者情况
    return movesSize < 9 ? "Pending" : "Draw";
}

[/et_pb_text]
[/et_pb_column]
[/et_pb_row]
[/et_pb_section]


她喜欢所以就做咯