[LeetCode] 1275. Find Winner on a Tic Tac Toe Game

[grandyang]

Tic-tac-toe is played by two players A and B on a 3 x 3 grid. The rules of Tic-Tac-Toe are:

• Players take turns placing characters into empty squares ' '.
• The first player A always places 'X' characters, while the second player B always places 'O' characters.
• 'X' and 'O' characters are always placed into empty squares, never on filled ones.
• The game ends when there are three of the same (non-empty) character filling any row, column, or diagonal.
• The game also ends if all squares are non-empty.
• No more moves can be played if the game is over.

Given a 2D integer array moves where moves[i] = [rowi, coli] indicates that the ith move will be played on grid[rowi][coli]. return  the winner of the game if it exists  (A or B). In case the game ends in a draw return "Draw". If there are still movements to play return "Pending".

You can assume that moves is valid (i.e., it follows the rules of Tic-Tac-Toe), the grid is initially empty, and A will play first.

Example 1:

Input: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Output: "A"
Explanation: A wins, they always play first.

Example 2:

Input: moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Output: "B"
Explanation: B wins.

Example 3:

Input: moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Output: "Draw"
Explanation: The game ends in a draw since there are no moves to make.

Example 4:

Input: moves = [[0,0],[1,1]]
Output: "Pending"
Explanation: The game has not finished yet.

Constraints:

• 1 <= moves.length <= 9
• moves[i].length == 2
• 0 <= rowi, coli <= 2
• There are no repeated elements on moves.
• moves follow the rules of tic tac toe.

这道题是关于井字棋游戏的，这个游戏简单容易上手，是课间十五分钟必备游戏之一，游戏规则很简单，一个人画叉，一个人画圆圈，只要有三个相连的位置，包括对角线就算赢。而这道题给了两个玩家的若干操作，让判断当前的棋盘状态，是哪一方赢了，还是没下完，或者是平局。判赢的条件就是找到任意行或列，或者对角线有三个相同的符号，若找不到有可能是平局或者没下完，只要判断总步数是否为9，就知道有没有下完了。由于给定的是两个玩家按顺序落子的位置，一个比较直接的方法就是分别还原出两个玩家在棋盘上的落子，分别还原出两个 3 by 3 的棋盘的好处是可以不用区分到底是叉还是圆圈，只要找三个连续的落子位置就行了，而且可以把查找逻辑放到一个子函数中进行复用。在子函数中，判断各行各列是否有连续三个落子，以及两条对角线，若有的话返回 true，否则 false。然后分别对还原出来的数组A和B调用子函数，若有返回的 true，则返回对应的A或B。否则就判断 moves 数组的长度，若等于9，返回平局 Draw，反之为 Pending，参见代码如下：

解法一：

class Solution {
public:
    string tictactoe(vector<vector<int>>& moves) {
        vector<vector<int>> A(3, vector<int>(3)), B = A;
        for (int i = 0; i < moves.size(); ++i) {
            if (i % 2 == 0) A[moves[i][0]][moves[i][1]] = 1;
            else B[moves[i][0]][moves[i][1]] = 1;
        }
        if (helper(A)) return "A";
        if (helper(B)) return "B";
        return (moves.size() == 9) ? "Draw" : "Pending";
    }
    bool helper(vector<vector<int>>& v) {
        for (int i = 0; i < 3; ++i) {
            if (v[i][0] == 1 && v[i][1] == 1 && v[i][2] == 1) return true;
            if (v[0][i] == 1 && v[1][i] == 1 && v[2][i] == 1) return true;
        }
        if (v[0][0] == 1 && v[1][1] == 1 && v[2][2] == 1) return true;
        if (v[2][0] == 1 && v[1][1] == 1 && v[0][2] == 1) return true;
        return false;
    }
};

再来看一种更简洁的写法，为了更好的区分玩家A和B落子，这里可以用1和 -1 来表示，这样若玩家A有三个相连的落子，则和为3，而玩家B的相连3个落子之和为 -3，只要判断各行各列以及对角线的和的绝对值，若为3，则肯定有玩家获胜，具体区分是哪个玩家，可以根据当前操作数的位置来判断，遍历 moves 数组时，若下标为偶数，则表示是玩家A，奇数则为玩家B，根据i的奇偶行来赋值 val 为1或 -1。取出落子位置的横纵坐标r和c，若二者相等，则是主对角线，diag 加上 val，若二者和为2，则是逆对角线，rev_diag 加上 val。然后 row 和 col 数组对应的位置加上 val，接下来判断行列对角线的和的绝对值是否有等于3的，有的话就根据 val 的正负来返回玩家A或B。否则就判断 moves 数组的长度，若等于9，返回平局 Draw，反之为 Pending，参见代码如下：

解法二：

class Solution {
public:
    string tictactoe(vector<vector<int>>& moves) {
        int diag = 0, rev_diag = 0;
        vector<int> row(3), col(3);
        for (int i = 0; i < moves.size(); ++i) {
            int r = moves[i][0], c = moves[i][1], val = i % 2 == 0 ? 1 : -1;
            if (r == c) diag += val;
            if (r + c == 2) rev_diag += val;
            row[r] += val;
            col[c] += val;
            if (abs(diag) == 3 || abs(rev_diag) == 3 || abs(row[r]) == 3 || abs(col[c]) == 3) return val == 1 ? "A" : "B";
        }
        return moves.size() == 9 ? "Draw" : "Pending";
    }
};

Github 同步地址:

#1275

参考资料：

https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game/

https://leetcode.com/problems/find-winner-on-a-tic-tac-toe-game/discuss/638224/Short-Java-code-using-diagonals-and-colrow-arrays

LeetCode All in One 题目讲解汇总(持续更新中...)

喜欢请点赞，疼爱请打赏❤️~.~

微信打赏

|

Venmo 打赏

---|---