Дано: В Крестики-нолики(Tic Tac Toe) играют два игрока A и B на сетке 3 x 3. Задан двумерный целочисленный массив moves, где moves[i] = [rowi, coli], в итоге на i-й ходе [rowi][coli], будет выявлен победитель, если он существует (A или B). В случае, если игра заканчивается вничью, возвращается "Ничья" (Draw). Если еще есть ходы, которые нужно сыграть, верните "Ожидание хода" (Pending).
Ответ должен содержать имя игрока A или B, Draw(Ничья) или Pending(Ожидание хода)
Ходы соответствуют правилам игры в Крестики-нолики, сетка изначально пуста, и игрок A будет играть первым.
Пример 1:
Дано: moves = [[0,0],[2,0],[1,1],[2,1],[2,2]]
Ответ: "A"
Пример 2:
Дано = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
Ответ: "B"
Пример 3:
Дано = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]]
Ответ: "Draw"
Ограничения:
1 <= moves.length <= 9
moves[i].length == 2
0 <= rowi, coli <= 2
В ходах нет повторяющихся элементов.
Ходы подчиняются правилам игры в крестики-нолики.
Решение:
class Solution:
def tictactoe(self, moves: List[List[int]]) -> str:
n = 3
rows, cols = [0] * n, [0] * n
d1, d2 = 0, 0
player = 1
for r, c in moves:
rows[r] += player
cols[c] += player
if r == c: d1 += player
if r + c == n - 1: d2 += player
if abs(rows[r]) == n or abs(cols[c]) == n or abs(d1) == n or abs(d2) == n:
if player == 1:
return "A"
else:
return "B"
player *= -1
if len(moves) == (n*n):
return "Draw"
else:
return "Pending"
Идея в отслеживании ходов по строкам, столбцам и диагоналям ( то есть, если что-то заполнено полностью одним игроком, то конец игры) - для этого мы задаём переменные rows, cols, d1, d2.
Также создаём переменную для контроля хода наших игроков - player A будет проходить цикл со значением переменной 1, и в конце каждого хода(цикла) меняем переменную для игрока В на значение -1, и так по кругу)
Дальше проходим по циклу: так как наш двумерный массив (список в списке) - то оказывается мы можем перебирать элементы внутреннего списка:
для двух элементов в подсписке: for x, y in array
для трех элементов в списке: for x, y, z in array
и т.д мы будем получать именно элементы во вложенном списке.
в итоге мы заполняем для каждого игрока наши созданные строки, столбцы, диагонали.
и в конце проверяем, заполнил ли один из игроков полностью одну из строк или столбцов row[i], col[i] (для нашего случая кто-нибудь должен был собрать 3 по модулю) или диагональ и возвращаем победителя, если таков нашелся, иначе продолжаем.
Временная сложность: O(len(moves))
Пространственная сложность: O(R + C), где R и C - количество строк и столбцов соответственно.