Помогите Решить задачу на Python . Заранее спасибо
После отборочного тура Технокубка вы нашли шахматную доску размера n x m
. Но вы не собираетесь играть в шахматы, так как вам опять предстоит решить задачу по программированию. А именно, вам нужно обрабатывать 3 вида запросов: 1 x y — поставить слона в клетку ( x ; y ). Гарантируется, что клетка пуста на момент поступления запроса. 2 x y
— убрать слона из клетки ( x ; y ). Гарантируется, что в клетке стоит слон на момент поступления запроса. 3 x y — рассмотрим всех слонов, которые сейчас стоят на доске. Для каждого вычислим минимальное число ходов, чтобы достичь клетки ( x ; y ) (если слон никогда не сможет достичь клетки, положим его равным бесконечности). Среди всех этих чисел необходимо найти минимальное.
Выведите ответ на каждый запрос третьего типа в новой строке. Если ответ равен бесконечности — выведите
−
1
.
Пример 1
Входные данные
20 8
10
1 15 4
3 13 6
3 10 2
3 3 8
1 2 7
3 3 8
2 15 4
3 13 6
1 20 8
3 10 2
Выходные данные
1
-1
3
1
2
3
Код:
from collections import deque
def bfs(start, target, n, m):
"""Поиск в ширину для поиска минимального пути от start до target на шахматном поле размера n x m."""
dx = [1, 1, -1, -1]
dy = [1, -1, 1, -1]
queue = deque([(start[0], start[1], 0)])
visited = set()
visited.add(start)
while queue:
x, y, moves = queue.popleft()
if (x, y) == target:
return moves
for i in range(4):
new_x, new_y = x + dx[i], y + dy[i]
while 1 <= new_x <= n and 1 <= new_y <= m: # Слон ходит по диагонали до края доски
if (new_x, new_y) not in visited:
queue.append((new_x, new_y, moves + 1))
visited.add((new_x, new_y))
new_x += dx[i]
new_y += dy[i]
return float('inf') # Если не достичь
def process_queries(n, m, queries):
elephants = set()
results = []
for query in queries:
if query[0] == 1:
x, y = query[1], query[2]
elephants.add((x, y))
elif query[0] == 2:
x, y = query[1], query[2]
elephants.remove((x, y))
elif query[0] == 3:
x, y = query[1], query[2]
min_moves = float('inf')
for elephant in elephants:
moves = bfs(elephant, (x, y), n, m)
if moves < min_moves:
min_moves = moves
if min_moves == float('inf'):
results.append(-1)
else:
results.append(min_moves)
return results
# Чтение входных данных
n, m = map(int, input().split())
q = int(input())
queries = []
for _ in range(q):
query = list(map(int, input().split()))
queries.append(query)
# Обработка запросов и вывод результатов
results = process_queries(n, m, queries)
for result in results:
print(result)