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 已显示.