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

😎 Решение:

var shortestPathBinaryMatrix = function(grid) {
    if (grid[0][0] !== 0 || grid[grid.length - 1][grid[0].length - 1] !== 0) {
        return -1;
    }

    const directions = [
        [-1, -1], [-1, 0], [-1, 1], 
        [0, -1], [0, 1], 
        [1, -1], [1, 0], [1, 1]
    ];

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

    while (queue.length > 0) {
        const [row, col] = queue.shift();
        const distance = grid[row][col];
        if (row === grid.length - 1 && col === grid[0].length - 1) {
            return distance;
        }
        for (const [dr, dc] of directions) {
            const newRow = row + dr;
            const newCol = col + dc;
            if (newRow >= 0 && newCol >= 0 && newRow < grid.length && newCol < grid[0].length && grid[newRow][newCol] === 0) {
                queue.push([newRow, newCol]);
                grid[newRow][newCol] = distance + 1;
            }
        }
    }
    return -1;
};

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