Сложность: hard
Имеется сетка размером 1 миллион на 1 миллион на плоскости XY, координаты каждого квадрата сетки - (x, y). Мы начинаем с исходного квадрата = [sx, sy] и хотим достичь цели = [tx, ty]. Существует также массив заблокированных квадратов, где каждый заблокированный[i] = [xi, yi] представляет собой заблокированный квадрат с координатами (xi, yi). Каждый ход мы можем пройти один квадрат на север, восток, юг или запад, если квадрат не находится в массиве заблокированных квадратов. Нам также не разрешается выходить за пределы сетки. Возвращается true тогда и только тогда, когда можно достичь целевого квадрата из исходного квадрата с помощью последовательности правильных ходов.
Пример:
Input: blocked = [[0,1],[1,0]], source = [0,0], target = [0,2]
Output: false
👨💻 Алгоритм:
1⃣Обработка входных данных:
Загрузите координаты исходного квадрата sx, sy, целевого квадрата tx, ty и список заблокированных квадратов blocked.
2⃣Проверка простого случая:
Если список blocked пуст, верните true, так как путь не будет заблокирован.
Проверка начальной или целевой клетки:
Если исходная или целевая клетка заблокированы, верните false.
3⃣Поиск пути с использованием BFS или DFS:
Используйте алгоритм поиска в ширину (BFS) или поиска в глубину (DFS) для поиска пути от sx, sy до tx, ty, избегая заблокированных клеток.
Если обнаружен путь, верните true, в противном случае верните false.
😎 Решение:
from collections import deque
def isEscapePossible(blocked, source, target):
blocked = set(map(tuple, blocked))
source = tuple(source)
target = tuple(target)
if source in blocked or target in blocked:
return False
def bfs(start, end):
queue = deque([start])
visited = set([start])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
max_area = len(blocked) * (len(blocked) - 1) // 2
while queue:
if len(visited) > max_area:
return True
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < 10**6 and 0 <= ny < 10**6 and (nx, ny) not in visited and (nx, ny) not in blocked:
if (nx, ny) == end:
return True
queue.append((nx, ny))
visited.add((nx, ny))
return False
return bfs(source, target) and bfs(target, source)
Ставь 👍 и забирай 📚 Базу знаний