505. The Maze II
В лабиринте есть мячик с пустыми пространствами (обозначенными как 0) и стенами (обозначенными как 1). Мячик может перемещаться через пустые пространства, катясь вверх, вниз, влево или вправо, но он не остановится, пока не столкнется со стеной. Когда мячик останавливается, он может выбрать следующее направление.
Дан лабиринт размером m x n, начальная позиция мяча и пункт назначения, где start = [startrow, startcol] и destination = [destinationrow, destinationcol]. return кратчайшее расстояние, на которое мячик должен остановиться в пункте назначения. Если мячик не может остановиться в пункте назначения, return -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# 해법
매칭됨/원본using 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++ 해법
자동 초안, 제출 전 검토#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 해법
매칭됨/원본public 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 해법
매칭됨/원본var 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 해법
매칭됨/원본from 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 해법
매칭됨/원본func 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]]
}Algorithm
Инициализация
Создайте 배열 distance для хранения минимальных расстояний до каждой позиции, инициализируйте его большими значениями. Установите начальную позицию start на нулевое расстояние и добавьте её в очередь.
Обход лабиринта
Используйте очередь для выполнения обхода в ширину (BFS). Для каждой позиции извлеките из очереди текущую позицию и исследуйте все возможные направления до столкновения со стеной, отслеживая количество шагов.
Обновление расстояний
Если достигнутая новая позиция может быть достигнута меньшим numberм шагов, обновите distance и добавьте эту позицию в очередь. После завершения обхода return минимальное расстояние до пункта назначения или -1, если его нельзя достичь.
😎
Vacancies for this task
활성 채용 with overlapping task tags are 표시됨.