← Static tasks

1091. Shortest Path in Binary Matrix

leetcode medium

#array#csharp#graph#leetcode#matrix#medium#queue#search

Task

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

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

Все посещенные клетки пути равны 0.

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

Длина чистого пути — это количество посещенных клеток этого пути.

Пример:

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

Output: 2

C# solution

matched/original
using System.Collections.Generic;
public class Solution {
    private static readonly int[][] directions = new int[][] {
        new int[] {-1, -1}, new int[] {-1, 0}, new int[] {-1, 1}, 
        new int[] {0, -1}, new int[] {0, 1}, 
        new int[] {1, -1}, new int[] {1, 0}, new int[] {1, 1}
    };
    public int ShortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] != 0 || grid[grid.Length - 1][grid[0].Length - 1] != 0) {
            return -1;
        }
        var queue = new Queue<int[]>();
        grid[0][0] = 1;
        queue.Enqueue(new int[] { 0, 0 });
        while (queue.Count > 0) {
            var cell = queue.Dequeue();
            int row = cell[0], col = cell[1], distance = grid[row][col];
            if (row == grid.Length - 1 && col == grid[0].Length - 1) {
                return distance;
            }
            foreach (var direction in directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                if (newRow >= 0 && newCol >= 0 && newRow < grid.Length && newCol < grid[0].Length && grid[newRow][newCol] == 0) {
                    queue.Enqueue(new int[] { newRow, newCol });
                    grid[newRow][newCol] = distance + 1;
                }
            }
        }
        return -1;
    }
}

C++ solution

auto-draft, review before submit
#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    private static readonly int[][] directions = new int[][] {
        new int[] {-1, -1}, new int[] {-1, 0}, new int[] {-1, 1}, 
        new int[] {0, -1}, new int[] {0, 1}, 
        new int[] {1, -1}, new int[] {1, 0}, new int[] {1, 1}
    };
    public int ShortestPathBinaryMatrix(int[][] grid) {
        if (grid[0][0] != 0 || grid[grid.size() - 1][grid[0].size() - 1] != 0) {
            return -1;
        }
        var queue = new queue<int[]>();
        grid[0][0] = 1;
        queue.Enqueue(new int[] { 0, 0 });
        while (queue.size() > 0) {
            var cell = queue.Dequeue();
            int row = cell[0], col = cell[1], distance = grid[row][col];
            if (row == grid.size() - 1 && col == grid[0].size() - 1) {
                return distance;
            }
            foreach (var direction in directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                if (newRow >= 0 && newCol >= 0 && newRow < grid.size() && newCol < grid[0].size() && grid[newRow][newCol] == 0) {
                    queue.Enqueue(new int[] { newRow, newCol });
                    grid[newRow][newCol] = distance + 1;
                }
            }
        }
        return -1;
    }
}

Java solution

matched/original
import java.util.*;

class Solution {
    private static final int[][] directions = {
        {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1}, {1, -1}, {1, 0}, {1, 1}
    };

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

        Queue<int[]> queue = new ArrayDeque<>();
        grid[0][0] = 1;
        queue.add(new int[]{0, 0});

        while (!queue.isEmpty()) {
            int[] cell = queue.remove();
            int row = cell[0], col = cell[1], distance = grid[row][col];
            if (row == grid.length - 1 && col == grid[0].length - 1) {
                return distance;
            }
            for (int[] direction : directions) {
                int newRow = row + direction[0];
                int newCol = col + direction[1];
                if (newRow >= 0 && newCol >= 0 && newRow < grid.length && newCol < grid[0].length && grid[newRow][newCol] == 0) {
                    queue.add(new int[]{newRow, newCol});
                    grid[newRow][newCol] = distance + 1;
                }
            }
        }
        return -1;
    }
}

JavaScript solution

matched/original
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;
};

Python solution

matched/original
from collections import deque

class Solution:
    directions = [(-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]

    def shortestPathBinaryMatrix(self, grid):
        if grid[0][0] != 0 or grid[-1][-1] != 0:
            return -1
        
        n = len(grid)
        queue = deque([(0, 0)])
        grid[0][0] = 1

        while queue:
            row, col = queue.popleft()
            distance = grid[row][col]
            if row == n - 1 and col == n - 1:
                return distance
            for dr, dc in self.directions:
                newRow, newCol = row + dr, col + dc
                if 0 <= newRow < n and 0 <= newCol < n and grid[newRow][newCol] == 0:
                    queue.append((newRow, newCol))
                    grid[newRow][newCol] = distance + 1
        return -1

Go solution

matched/original
package main

import "container/list"

func shortestPathBinaryMatrix(grid [][]int) int {
    if grid[0][0] != 0 || grid[len(grid)-1][len(grid[0])-1] != 0 {
        return -1
    }

    directions := [][]int{
        {-1, -1}, {-1, 0}, {-1, 1}, {0, -1}, {0, 1},
        {1, -1}, {1, 0}, {1, 1},
    }

    queue := list.New()
    queue.PushBack([]int{0, 0})
    grid[0][0] = 1

    for queue.Len() > 0 {
        cell := queue.Remove(queue.Front()).([]int)
        row, col := cell[0], cell[1]
        distance := grid[row][col]
        if row == len(grid)-1 && col == len(grid[0])-1 {
            return distance
        }
        for _, direction := range directions {
            newRow, newCol := row+direction[0], col+direction[1]
            if newRow >= 0 && newCol >= 0 && newRow < len(grid) && newCol < len(grid[0]) && grid[newRow][newCol] == 0 {
                queue.PushBack([]int{newRow, newCol})
                grid[newRow][newCol] = distance + 1
            }
        }
    }
    return -1
}

Explanation

Algorithm

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

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

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

😎