1275. Find Winner on a Tic Tac Toe Game
Description
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 playerB
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.
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.
Solutions
Solution 1: Determine if the last player to move can win
Since all moves
are valid, that is, there is no situation where a person continues to play after someone has won. Therefore, we only need to determine whether the last player to move can win.
We use an array cnt
of length $8$ to record the number of moves in rows, columns, and diagonals. Where $cnt[0, 1, 2]$ represent the number of moves in the $0, 1, 2$ rows respectively, and $cnt[3, 4, 5]$ represent the number of moves in the $0, 1, 2$ columns respectively. Additionally, $cnt[6]$ and $cnt[7]$ represent the number of moves on the two diagonals respectively. During the game, if a player makes $3$ moves in a row, column, or diagonal, that player wins.
If the last player to move does not win, then we determine whether the board is full. If it is full, it is a draw; otherwise, the game is not over yet.
The time complexity is $O(n)$, and the space complexity is $O(n)$. Where $n$ is the length of moves
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
|