Помогите Решить задачу на Python . Заранее спасибо

Question

Помогите Решить задачу на Python . Заранее спасибо

Meps Mepsikovich Ученик (73), открыт 1 неделю назад

После отборочного тура Технокубка вы нашли шахматную доску размера 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

Answer 1

Код:

 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)