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 表示.