Sponsored
Sponsored
In this approach, we use a 3x3 board to simulate the mechanics of a Tic Tac Toe game. For every move made, we place the respective player's symbol ('X' for player A and 'O' for player B) on the board. After each move, we check if this move results in a win for any player by verifying if there are three matching symbols in any row, column, or diagonal. If a win is found, that player is declared the winner and the game ends. If all moves are exhausted without a winner, the game is declared a draw. If there are remaining moves, the game is pending.
Time Complexity: O(n), where n is the length of the moves. In the worst case, it checks 8 winning conditions for all 9 moves.
Space Complexity: O(1), since the board is of fixed size (3x3).
1#include <iostream>
2#include <vector>
3using namespace std;
4
5string tictactoe(vector<vector<int>>& moves) {
6 char board[3][3] = {{' ', ' ', ' '},{' ', ' ', ' '},{' ', ' ', ' '}};
7 char player = 'X';
8 for (auto& move : moves) {
9 board[move[0]][move[1]] = player;
10 player = (player == 'X') ? 'O' : 'X';
11 }
12 for (int i = 0; i < 3; ++i) {
13 if (board[i][0] != ' ' && board[i][0] == board[i][1] && board[i][1] == board[i][2])
return (board[i][0] == 'X') ? "A" : "B";
if (board[0][i] != ' ' && board[0][i] == board[1][i] && board[1][i] == board[2][i])
return (board[0][i] == 'X') ? "A" : "B";
}
if (board[0][0] != ' ' && board[0][0] == board[1][1] && board[1][1] == board[2][2])
return (board[0][0] == 'X') ? "A" : "B";
if (board[0][2] != ' ' && board[0][2] == board[1][1] && board[1][1] == board[2][0])
return (board[0][2] == 'X') ? "A" : "B";
return moves.size() == 9 ? "Draw" : "Pending";
}
int main() {
vector<vector<int>> moves = {{0,0},{2,0},{1,1},{2,1},{2,2}};
cout << tictactoe(moves) << endl;
return 0;
}
The C++ solution uses a similar logic to the C solution but utilizes a C++ vector to store the moves. The main goal is to iterate through all moves, updating the board, and after each move, check for whether any player has won the game using row, column, and diagonal checks.
Instead of simulating the grid itself, this approach tracks the status of each row, column, and the two diagonals using counters. Each player will have their counters, incrementing or decrementing upon making a move. The first instance a counter reaches 3 or -3 indicates a player has won the game. This method significantly reduces the need to check the grid extensively for each move while still adhering to the rules of Tic Tac Toe.
Time Complexity: O(n), where n is the number of moves.
Space Complexity: O(1), as only fixed-size counters are involved.
public class Solution {
public string Tictactoe(int[][] moves) {
int[] row = new int[3];
int[] col = new int[3];
int diag = 0, antiDiag = 0;
int player = 1;
foreach (var move in moves) {
int r = move[0], c = move[1];
row[r] += player;
col[c] += player;
if (r == c) diag += player;
if (r + c == 2) antiDiag += player;
if (Math.Abs(row[r]) == 3 || Math.Abs(col[c]) == 3 || Math.Abs(diag) == 3 || Math.Abs(antiDiag) == 3)
return player == 1 ? "A" : "B";
player *= -1;
}
return moves.Length == 9 ? "Draw" : "Pending";
}
public static void Main(string[] args) {
int[][] moves = new int[][] { new int[] {0,0}, new int[] {2,0}, new int[] {1,1}, new int[] {2,1}, new int[] {2,2} };
Solution sol = new Solution();
Console.WriteLine(sol.Tictactoe(moves));
}
}
This C# code relies on incremental modifications for respective player counters. Configured for efficient win detection through arithmetic thresholds, the counters facilitate an immediate response when a victorious alignment is effectively structed.