505. The Maze II
leetcode medium
Task
В лабиринте есть мячик с пустыми пространствами (обозначенными как 0) и стенами (обозначенными как 1). Мячик может перемещаться через пустые пространства, катясь вверх, вниз, влево или вправо, но он не остановится, пока не столкнется со стеной. Когда мячик останавливается, он может выбрать следующее направление.
Дан лабиринт размером m x n, начальная позиция мяча и пункт назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. Верните кратчайшее расстояние, на которое мячик должен остановиться в пункте назначения. Если мячик не может остановиться в пункте назначения, верните -1.
Расстояние — это количество пройденных пустых пространств мячиком от начальной позиции (исключительно) до пункта назначения (включительно).
Предположим, что границы лабиринта — это стены. В примере ниже они не указаны.
Пример:
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: 12
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.
C# solution
matched/originalusing System;
using System.Collections.Generic;
public class Solution {
public int ShortestDistance(int[][] maze, int[] start, int[] destination) {
int m = maze.Length, n = maze[0].Length;
int[][] distance = new int[m][];
for (int i = 0; i < m; i++) {
distance[i] = new int[n];
Array.Fill(distance[i], int.MaxValue);
}
distance[start[0]][start[1]] = 0;
int[][] directions = new int[][] { new int[] { 0, 1 }, new int[] { 0, -1 }, new int[] { -1, 0 }, new int[] { 1, 0 } };
Queue<int[]> queue = new Queue<int[]>();
queue.Enqueue(start);
while (queue.Count > 0) {
int[] s = queue.Dequeue();
foreach (var dir in directions) {
int x = s[0] + dir[0], y = s[1] + dir[1], count = 0;
while (x >= 0 && y >= 0 && x < m && y < n && maze[x][y] == 0) {
x += dir[0];
y += dir[1];
count++;
}
x -= dir[0];
y -= dir[1];
if (distance[s[0]][s[1]] + count < distance[x][y]) {
distance[x][y] = distance[s[0]][s[1]] + count;
queue.Enqueue(new int[] { x, y });
}
}
}
return distance[destination[0]][destination[1]] == int.MaxValue ? -1 : distance[destination[0]][destination[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:
public int ShortestDistance(int[][] maze, vector<int>& start, vector<int>& destination) {
int m = maze.size(), n = maze[0].size();
int[][] distance = new int[m][];
for (int i = 0; i < m; i++) {
distance[i] = new int[n];
Array.Fill(distance[i], int.MaxValue);
}
distance[start[0]][start[1]] = 0;
int[][] directions = new int[][] { new int[] { 0, 1 }, new int[] { 0, -1 }, new int[] { -1, 0 }, new int[] { 1, 0 } };
queue<int[]> queue = new queue<int[]>();
queue.Enqueue(start);
while (queue.size() > 0) {
vector<int>& s = queue.Dequeue();
foreach (var dir in directions) {
int x = s[0] + dir[0], y = s[1] + dir[1], count = 0;
while (x >= 0 && y >= 0 && x < m && y < n && maze[x][y] == 0) {
x += dir[0];
y += dir[1];
count++;
}
x -= dir[0];
y -= dir[1];
if (distance[s[0]][s[1]] + count < distance[x][y]) {
distance[x][y] = distance[s[0]][s[1]] + count;
queue.Enqueue(new int[] { x, y });
}
}
}
return distance[destination[0]][destination[1]] == int.MaxValue ? -1 : distance[destination[0]][destination[1]];
}
}Java solution
matched/originalpublic class Solution {
public int shortestDistance(int[][] maze, int[] start, int[] dest) {
int[][] distance = new int[maze.length][maze[0].length];
for (int[] row: distance)
Arrays.fill(row, Integer.MAX_VALUE);
distance[start[0]][start[1]] = 0;
int[][] dirs={{0, 1} ,{0, -1}, {-1, 0}, {1, 0}};
Queue < int[] > queue = new LinkedList < > ();
queue.add(start);
while (!queue.isEmpty()) {
int[] s = queue.remove();
for (int[] dir: dirs) {
int x = s[0] + dir[0];
int y = s[1] + dir[1];
int count = 0;
while (x >= 0 && y >= 0 && x < maze.length && y < maze[0].length && maze[x][y] == 0) {
x += dir[0];
y += dir[1];
count++;
}
if (distance[s[0]][s[1]] + count < distance[x - dir[0]][y - dir[1]]) {
distance[x - dir[0]][y - dir[1]] = distance[s[0]][s[1]] + count;
queue.add(new int[] {x - dir[0], y - dir[1]});
}
}
}
return distance[dest[0]][dest[1]] == Integer.MAX_VALUE ? -1 : distance[dest[0]][dest[1]];
}
}JavaScript solution
matched/originalvar shortestDistance = function(maze, start, destination) {
const m = maze.length, n = maze[0].length;
const distance = Array.from({ length: m }, () => Array(n).fill(Infinity));
distance[start[0]][start[1]] = 0;
const directions = [[0, 1], [0, -1], [-1, 0], [1, 0]];
const queue = [start];
while (queue.length) {
const [sx, sy] = queue.shift();
for (const [dx, dy] of directions) {
let x = sx + dx, y = sy + dy, count = 0;
while (x >= 0 && y >= 0 && x < m && y < n && maze[x][y] === 0) {
x += dx;
y += dy;
count++;
}
x -= dx;
y -= dy;
if (distance[sx][sy] + count < distance[x][y]) {
distance[x][y] = distance[sx][sy] + count;
queue.push([x, y]);
}
}
}
const res = distance[destination[0]][destination[1]];
return res === Infinity ? -1 : res;
};Python solution
matched/originalfrom collections import deque
class Solution:
def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
m, n = len(maze), len(maze[0])
distance = [[float('inf')] * n for _ in range(m)]
distance[start[0]][start[1]] = 0
directions = [(0, 1), (0, -1), (-1, 0), (1, 0)]
queue = deque([start])
while queue:
s = queue.popleft()
for dx, dy in directions:
x, y, count = s[0] + dx, s[1] + dy, 0
while 0 <= x < m and 0 <= y < n and maze[x][y] == 0:
x += dx
y += dy
count += 1
x -= dx
y -= dy
if distance[s[0]][s[1]] + count < distance[x][y]:
distance[x][y] = distance[s[0]][s[1]] + count
queue.append([x, y])
return -1 if distance[destination[0]][destination[1]] == float('inf') else distance[destination[0]][destination[1]]Go solution
matched/originalfunc shortestDistance(maze [][]int, start []int, destination []int) int {
m, n := len(maze), len(maze[0])
distance := make([][]int, m)
for i := range distance {
distance[i] = make([]int, n)
for j := range distance[i] {
distance[i][j] = 1<<31 - 1
}
}
distance[start[0]][start[1]] = 0
directions := [][]int{{0, 1}, {0, -1}, {-1, 0}, {1, 0}}
queue := [][]int{start}
for len(queue) > 0 {
s := queue[0]
queue = queue[1:]
for _, dir := range directions {
x, y, count := s[0]+dir[0], s[1]+dir[1], 0
for x >= 0 && y >= 0 && x < m && y < n && maze[x][y] == 0 {
x += dir[0]
y += dir[1]
count++
}
x -= dir[0]
y -= dir[1]
if distance[s[0]] [s[1]]+count < distance[x][y] {
distance[x][y] = distance[s[0]][s[1]] + count
queue = append(queue, []int{x, y})
}
}
}
if distance[destination[0]][destination[1]] == 1<<31-1 {
return -1
}
return distance[destination[0]][destination[1]]
}Explanation
Algorithm
Инициализация
Создайте массив distance для хранения минимальных расстояний до каждой позиции, инициализируйте его большими значениями. Установите начальную позицию start на нулевое расстояние и добавьте её в очередь.
Обход лабиринта
Используйте очередь для выполнения обхода в ширину (BFS). Для каждой позиции извлеките из очереди текущую позицию и исследуйте все возможные направления до столкновения со стеной, отслеживая количество шагов.
Обновление расстояний
Если достигнутая новая позиция может быть достигнута меньшим числом шагов, обновите distance и добавьте эту позицию в очередь. После завершения обхода верните минимальное расстояние до пункта назначения или -1, если его нельзя достичь.
😎