Задача: 1036. Escape a Large Maze
Сложность: 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.

😎 Решение:

class Solution {
    func isEscapePossible(_ blocked: [[Int]], _ source: [Int], _ target: [Int]) -> Bool {
        let blockedSet = Set(blocked.map { ($0[0], $0[1]) })
        let source = (source[0], source[1])
        let target = (target[0], target[1])
        
        if blockedSet.contains(source) || blockedSet.contains(target) {
            return false
        }
        
        func bfs(_ start: (Int, Int), _ end: (Int, Int)) -> Bool {
            var queue = [(start.0, start.1)]
            var visited = Set([(start.0, start.1)])
            let directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]
            let maxArea = blocked.count * (blocked.count - 1) / 2
            
            while !queue.isEmpty {
                if visited.count > maxArea {
                    return true
                }
                let (x, y) = queue.removeFirst()
                for (dx, dy) in directions {
                    let nx = x + dx, ny = y + dy
                    if nx >= 0 && nx < 1_000_000 && ny >= 0 && ny < 1_000_000 && !visited.contains((nx, ny)) && !blockedSet.contains((nx, ny)) {
                        if (nx, ny) == end {
                            return true
                        }
                        queue.append((nx, ny))
                        visited.insert((nx, ny))
                    }
                }
            }
            return false
        }
        
        return bfs(source, target) && bfs(target, source)
    }
}

Ставь 👍 и забирай 📚 Базу знаний