Задача: 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.

😎 Решение:

var isEscapePossible = function(blocked, source, target) {
    const blockedSet = new Set(blocked.map(b => `${b[0]},${b[1]}`));
    const src = `${source[0]},${source[1]}`;
    const tgt = `${target[0]},${target[1]}`;
    
    if (blockedSet.has(src) || blockedSet.has(tgt)) return false;
    
    const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    const maxArea = blocked.length * (blocked.length - 1) / 2;
    
    const bfs = (start, end) => {
        const queue = [start];
        const visited = new Set([start]);
        
        while (queue.length) {
            if (visited.size > maxArea) return true;
            const [x, y] = queue.shift().split(',').map(Number);
            for (const [dx, dy] of directions) {
                const nx = x + dx, ny = y + dy;
                const next = `${nx},${ny}`;
                if (nx >= 0 && nx < 1_000_000 && ny >= 0 && ny < 1_000_000 && !visited.has(next) && !blockedSet.has(next)) {
                    if (next === end) return true;
                    queue.push(next);
                    visited.add(next);
                }
            }
        }
        return false;
    };
    
    return bfs(src, tgt) && bfs(tgt, src);
};

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