Задача: 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 let directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    
    func shortestPathBinaryMatrix(_ grid: [[Int]]) -> Int {
        if grid[0][0] != 0 || grid[grid.count - 1][grid[0].count - 1] != 0 {
            return -1
        }
        
        var grid = grid
        var queue: [(Int, Int)] = [(0, 0)]
        grid[0][0] = 1
        
        while !queue.isEmpty {
            let (row, col) = queue.removeFirst()
            let distance = grid[row][col]
            if row == grid.count - 1 && col == grid[0].count - 1 {
                return distance
            }
            for direction in directions {
                let newRow = row + direction.0
                let newCol = col + direction.1
                if newRow >= 0 && newCol >= 0 && newRow < grid.count && newCol < grid[0].count && grid[newRow][newCol] == 0 {
                    queue.append((newRow, newCol))
                    grid[newRow][newCol] = distance + 1
                }
            }
        }
        return -1
    }
}

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