Задача яндекса python, помогите решить пж
условия:
A. Бесконечные крестики-нолики
Ограничение времени 2 секунды
Ограничение памяти 256Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Игра в крестики-нолики на бесконечной плоскости похожа на обычные крестики-нолики: два игрока по очереди ставят свои фигуры (крестики у первого игрока и нолики — у второго) в свободные клетки поля. Побеждает тот игрок, который первым выстроил пять своих фигур по горизонтали, вертикали или одной из диагоналей.
В логе записаны координаты клеток, в том порядке, в котором игроки ставили свои фигуры. Определите, кто победил в игре или отследите ситуацию, что игроки увлеклись и продолжили игру после победы одного из игроков.
Формат ввода
В первой строке записано число n (1 ≤ n ≤ 10000) — количество ходов, которые совершили игроки.
В следующих n строках записано по два числа r, c (|r|, |c| ≤ 109) — координаты клетки, в которую была поставлена очередная фигура. Гарантируется, что все координаты клеток уникальны (т.е. игрок не ставил свою фигуру в ту клетку, в которой уже стоит фигура)
Формат вывода
В случае победы первого игрока последним ходом выведите слово ”First”. В случае победы второго игрока последним ходом выведите слово ”Second”. Если ни один из игроков не успел победить выведите слово ”Draw”. Если ходы продолжились после победы одного из игроков выведите слово ”Inattention”.
Пример 1
Ввод Вывод
9
4 4
4 5
2 2
2 3
3 3
3 4
1 1
1 2
5 5
First
Пример 2
Ввод Вывод
10
5 0
1 1
4 0
2 1
3 0
3 1
2 0
4 1
1 0
5 1
Inattention
код:
def check_win(moves):
def win(player_moves, last_move):
directions = [(1, 0), (0, 1), (1, 1), (1, -1)]
count = 1
for dx, dy in directions:
for i in range(1, 5):
if (last_move[0] + dx*i, last_move[1] + dy*i) in player_moves:
count += 1
else:
break
for i in range(1, 5):
if (last_move[0] - dx*i, last_move[1] - dy*i) in player_moves:
count += 1
else:
break
if count >= 5:
return True
return False
player_moves = [{}, {}]
winner = None
for i, (r, c) in enumerate(moves):
current_player = i % 2
player_moves[current_player][(r, c)] = True
if win(player_moves[current_player], (r, c)):
winner = "First" if current_player == 0 else "Second"
break
if winner != None:
if i + 1 < len(moves):
return "Inattention"
else:
return winner
else:
return "Draw"
#ввод
n = int(input().strip())
moves = [tuple(map(int, input().split())) for _ in range(n)]
#вывод
print(check_win(moves))
вопрос:
почему-то ввод/вывод не работают((
def check_win(moves):
def win(player_moves, last_move):
directions = [(1, 0), (0, 1), (1, 1), (1, -1)]
for dx, dy in directions:
count = 1
for i in range(1, 5):
for sign in [-1, 1]:
if (last_move[0] + sign * dx * i, last_move[1] + sign * dy * i) in player_moves:
count += 1
else:
break
if count >= 5:
return True
return False
player_moves = [set(), set()]
winner = None
for i, (r, c) in enumerate(moves):
current_player = i % 2
player_moves[current_player].add((r, c))
if win(player_moves[current_player], (r, c)):
winner = "First" if current_player == 0 else "Second"
break
if winner != None:
if i + 1 < len(moves):
return "Inattention"
else:
return winner
else:
return "Draw"
# Ввод
n = int(input().strip())
moves = [tuple(map(int, input().split())) for _ in range(n) if input()]
# Вывод
print(check_win(moves)) Для решения этой задачи следует создать функцию, которая будет анализировать каждый ход, обновляя состояние "бесконечной" игровой плоскости и проверяя условия победы после каждого хода. Для упрощения можно использовать словарь или хеш-таблицу для хранения состояния игры, используя координаты для ключей и метки игроков ('X' или 'O') для значений.
Проверку на победу можно эффективно проводить, анализируя только клетки вокруг последнего хода, так как только эти клетки могут образовать выигрышную линию длиной в пять фигур.
Рассмотрим псевдокод возможного решения:
def check_win(board, x, y, symbol):
directions = [(0, 1), (1, 0), (1, 1), (1, -1)] # горизонталь, вертикаль, две диагонали
for dx, dy in directions:
count = 1
# проверяем в одном направлении
for i in range(1, 5):
if (x + dx*i, y + dy*i) in board and board[(x + dx*i, y + dy*i)] == symbol:
count += 1
else:
break
# проверяем в противоположном направлении
for i in range(1, 5):
if (x - dx*i, y - dy*i) in board and board[(x - dx*i, y - dy*i)] == symbol:
count += 1
else:
break
if count >= 5:
return True
return False
def solve(n, moves):
board = {}
winner_declared = False
for i, (x, y) in enumerate(moves):
symbol = 'X' if i % 2 == 0 else 'O'
board[(x, y)] = symbol
if check_win(board, x, y, symbol) and not winner_declared:
print("First" if symbol == 'X' else "Second")
winner_declared = True
elif winner_declared: # Если победитель уже был объявлен
return "Inattention"
return "Draw" if not winner_declared else "Inattention"
n = int(input())
moves = []
for _ in range(n):
r, c = map(int, input().split())
moves.append((r, c))
print(solve(n, moves))
print(solve(n, moves))
Этот код сначала инициализирует игровое поле как пустой словарь, затем в цикле обрабатывает каждый ход, записывая в словарь фигуру текущего игрока по указанным координатам. Для каждого хода вызывается функция проверки на победу, которая возвращает True, если текущий ход образовал выигрышную комбинацию. Если функция обнаруживает победу, код выводит имя победившего игрока. Если после объявления победителя ходы продолжаются, выводится "Inattention". Если победитель не определен после всех ходов, выводится "Draw".
Попробуй так:
def check_win(moves):
def win(player_moves, last_move):
directions = [(1, 0), (0, 1), (1, 1), (1, -1)]
for dx, dy in directions:
count = 1
for i in range(1, 5):
if (last_move[0] + dx * i, last_move[1] + dy * i) in player_moves:
count += 1
else:
break
for i in range(1, 5):
if (last_move[0] - dx * i, last_move[1] - dy * i) in player_moves:
count += 1
else:
break
if count >= 5:
return True
return False
player_moves = [set(), set()]
winner = None
for i, (r, c) in enumerate(moves):
current_player = i % 2
player_moves[current_player].add((r, c))
if win(player_moves[current_player], (r, c)):
winner = "First" if current_player == 0 else "Second"
break
if winner:
if i + 1 < len(moves):
return "Inattention"
else:
return winner
else:
return "Draw"
n = int(input().strip())
moves = [tuple(map(int, input().split())) for _ in range(n)]
print(check_win(moves))