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

😎 Решение:

function isEscapePossible($blocked, $source, $target) {
    $blockedSet = [];
    foreach ($blocked as $b) {
        $blockedSet["{$b[0]},{$b[1]}"] = true;
    }
    $src = "{$source[0]},{$source[1]}";
    $tgt = "{$target[0]},{$target[1]}";
    
    if (isset($blockedSet[$src]) || isset($blockedSet[$tgt])) return false;

    $directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
    $maxArea = count($blocked) * (count($blocked) - 1) / 2;

    function bfs($start, $end, $blockedSet, $directions, $maxArea) {
        $queue = [$start];
        $visited = [$start => true];

        while ($queue) {
            if (count($visited) > $maxArea) return true;
            list($x, $y) = explode(',', array_shift($queue));
            foreach ($directions as $dir) {
                $nx = $x + $dir[0];
                $ny = $y + $dir[1];
                $next = "{$nx},{$ny}";
                if ($nx >= 0 && $nx < 1000000 && $ny >= 0 && $ny < 1000000 && !isset($visited[$next]) && !isset($blockedSet[$next])) {
                    if ($next === $end) return true;
                    $queue[] = $next;
                    $visited[$next] = true;
                }
            }
        }
        return false;
    }
    
    return bfs($src, $tgt, $blockedSet, $directions, $maxArea) && bfs($tgt, $src, $blockedSet, $directions, $maxArea);
}

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