Задача: 505. The Maze II
Сложность: medium

Дан лабиринт, где 0 — пустая ячейка, 1 — стена.
Мячик может катиться по пустым клеткам, пока не упадёт в стену.
Нужно найти минимальное количество шагов, чтобы добраться от start до destination, где шаг — это каждое пустое пространство. Если добраться нельзя — вернуть -1.

Пример:

Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: 12
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

👨‍💻 Алгоритм:

1⃣Инициализация
Создайте массив distance для хранения минимальных расстояний до каждой позиции, инициализируйте его большими значениями. Установите начальную позицию start на нулевое расстояние и добавьте её в очередь.

2⃣Обход лабиринта
Используйте очередь для выполнения обхода в ширину (BFS). Для каждой позиции извлеките из очереди текущую позицию и исследуйте все возможные направления до столкновения со стеной, отслеживая количество шагов.

3⃣Обновление расстояний
Если достигнутая новая позиция может быть достигнута меньшим числом шагов, обновите distance и добавьте эту позицию в очередь. После завершения обхода верните минимальное расстояние до пункта назначения или -1, если его нельзя достичь.

😎 Решение:

class Solution {
    function shortestDistance($maze, $start, $destination) {
        $m = count($maze);
        $n = count($maze[0]);
        $distance = array_fill(0, $m, array_fill(0, $n, PHP_INT_MAX));
        $distance[$start[0]][$start[1]] = 0;
        $directions = [[0, 1], [0, -1], [-1, 0], [1, 0]];
        $queue = [[$start[0], $start[1]]];
        
        while (!empty($queue)) {
            list($sx, $sy) = array_shift($queue);
            foreach ($directions as list($dx, $dy)) {
                $x = $sx + $dx;
                $y = $sy + $dy;
                $count = 0;
                while ($x >= 0 && $y >= 0 && $x < $m && $y < $n && $maze[$x][$y] == 0) {
                    $x += $dx;
                    $y += $dy;
                    $count++;
                }
                $x -= $dx;
                $y -= $dy;
                if ($distance[$sx][$sy] + $count < $distance[$x][$y]) {
                    $distance[$x][$y] = $distance[$sx][$sy] + $count;
                    array_push($queue, [$x, $y]);
                }
            }
        }
        
        return $distance[$destination[0]][$destination[1]] == PHP_INT_MAX ? -1 : $distance[$destination[0]][$destination[1]];
    }
}

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