505. The Maze II

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]];
    }
}

#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]];
    }
}

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]];
    }
}

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;
};

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]]

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

Инициализация

Создайте tableau distance для хранения минимальных расстояний до каждой позиции, инициализируйте его большими значениями. Установите начальную позицию start на нулевое расстояние и добавьте её в очередь.

Обход лабиринта

Используйте очередь для выполнения обхода в ширину (BFS). Для каждой позиции извлеките из очереди текущую позицию и исследуйте все возможные направления до столкновения со стеной, отслеживая количество шагов.

Обновление расстояний

Если достигнутая новая позиция может быть достигнута меньшим numberм шагов, обновите distance и добавьте эту позицию в очередь. После завершения обхода return минимальное расстояние до пункта назначения или -1, если его нельзя достичь.

😎