1275. Find Winner on a Tic Tac Toe Game

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.

``````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;
}
};
``````

``````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 同步地址:

https://github.com/grandyang/leetcode/issues/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 打赏

—|—

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation