Задача: 499. The Maze III
Сложность: hard

В лабиринте есть мячик с пустыми пространствами (0) и стенами (1). Мячик может катиться вверх, вниз, влево или вправо, пока не столкнется со стеной, затем выбрать новое направление. В лабиринте также есть отверстие, куда мячик упадет, если закатится в него.
Дан лабиринт размером m x n, позиция мяча ball и отверстия hole, где ball = [ballrow, ballcol] и hole = [holerow, holecol]. Верните строку instructions с кратчайшим путем мячика к отверстию. Если существует несколько вариантов, верните лексикографически минимальный. Если путь невозможен, верните "impossible". Ответ должен содержать 'u' (вверх), 'd' (вниз), 'l' (влево) и 'r' (вправо).
Расстояние — это количество пройденных пустых пространств от начальной позиции (исключительно) до конечной (включительно).
Вы можете предположить, что границы лабиринта — это стены. В примере ниже они не указаны.

Пример:

Input: maze = [[0,0,0,0,0],[1,1,0,0,1],[0,0,0,0,0],[0,1,0,0,1],[0,1,0,0,0]], ball = [4,3], hole = [0,1]
Output: "lul"

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

1⃣Инициализация и вспомогательные функции
Создайте функцию valid для проверки, находится ли координата (row, col) в пределах лабиринта и является ли она пустым пространством. Создайте функцию getNeighbors для получения списка соседей для данной позиции. Двигайтесь в каждом направлении (вверх, вниз, влево, вправо) до встречи со стеной.

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

3⃣Поиск кратчайшего пути
Пока очередь не пуста, извлекайте узел с наименьшим расстоянием. Если узел посещен, пропустите его. Если это отверстие, верните текущий путь. Отметьте узел как посещенный, добавьте его соседей в очередь, обновив расстояние и путь. Если пути нет, верните "impossible".

😎 Решение:

class State {
    public $row, $col, $dist, $path;
    public function __construct($r, $c, $d, $p) {
        $this->row = $r; $this->col = $c; $this->dist = $d; $this->path = $p;
    }
}

class MinHeap extends SplMinHeap {
    protected function compare($a, $b) {
        return $a->dist === $b->dist ? strcmp($a->path, $b->path) : $a->dist - $b->dist;
    }
}

class Solution {
    private $dirs = [[0, -1], [-1, 0], [0, 1], [1, 0]];
    private $dirText = ["l", "u", "r", "d"];

    function findShortestWay($maze, $ball, $hole) {
        $m = count($maze); $n = count($maze[0]);
        $heap = new MinHeap();
        $seen = array_fill(0, $m, array_fill(0, $n, false));
        $heap->insert(new State($ball[0], $ball[1], 0, ""));
        
        while (!$heap->isEmpty()) {
            $curr = $heap->extract();
            if ($seen[$curr->row][$curr->col]) continue;
            if ($curr->row == $hole[0] && $curr->col == $hole[1]) return $curr->path;
            $seen[$curr->row][$curr->col] = true;

            foreach ($this->dirs as $i => [$dy, $dx]) {
                $r = $curr->row; $c = $curr->col; $dist = 0;
                while ($r + $dy >= 0 && $r + $dy < $m && $c + $dx >= 0 && $c + $dx < $n && $maze[$r + $dy][$c + $dx] == 0) {
                    $r += $dy; $c += $dx; $dist++;
                    if ($r == $hole[0] && $c == $hole[1]) break;
                }
                $heap->insert(new State($r, $c, $curr->dist + $dist, $curr->path . $this->dirText[$i]));
            }
        }
        return "impossible";
    }
}

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