Задача: 1091. Shortest Path in Binary Matrix
Сложность: medium

Дан бинарный матричный массив grid размером n x n. Верните длину самого короткого чистого пути в матрице. Если чистого пути не существует, верните -1.

Чистый путь в бинарной матрице — это путь из верхнего левого угла (т.е. (0, 0)) в нижний правый угол (т.е. (n - 1, n - 1)), такой что:

Все посещенные клетки пути равны 0.
Все соседние клетки пути соединены по 8 направлениям (т.е. они различны и имеют общую сторону или угол).
Длина чистого пути — это количество посещенных клеток этого пути.

Пример:

Input: grid = [[0,1],[1,0]]
Output: 2

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

1⃣Проверить, что начальная и конечная клетки открыты (равны 0). Если нет, вернуть -1.

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

3⃣Если достигнута конечная клетка, вернуть длину пути. Если очередь пуста и конечная клетка не достигнута, вернуть -1.

😎 Решение:

class Solution {
    private static $directions = [
        [-1, -1], [-1, 0], [-1, 1],
        [0, -1], [0, 1],
        [1, -1], [1, 0], [1, 1]
    ];

    function shortestPathBinaryMatrix($grid) {
        if ($grid[0][0] != 0 || $grid[count($grid) - 1][count($grid[0]) - 1] != 0) {
            return -1;
        }

        $queue = [[0, 0]];
        $grid[0][0] = 1;

        while (!empty($queue)) {
            [$row, $col] = array_shift($queue);
            $distance = $grid[$row][$col];
            if ($row == count($grid) - 1 && $col == count($grid[0]) - 1) {
                return $distance;
            }
            foreach (self::$directions as $direction) {
                $newRow = $row + $direction[0];
                $newCol = $col + $direction[1];
                if ($newRow >= 0 && $newCol >= 0 && $newRow < count($grid) && $newCol < count($grid[0]) && $grid[$newRow][$newCol] == 0) {
                    $queue[] = [$newRow, $newCol];
                    $grid[$newRow][$newCol] = $distance + 1;
                }
            }
        }
        return -1;
    }
}

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