LeetCode 505. 迷宫 II

Categories:

题目描述
思路分析
1. 解法一：Dijkstra 最短路（推荐）
相似题目

题目描述

✅ 505. 迷宫 II

思路分析

解法一：Dijkstra 最短路（推荐）

核心思路：

每次滚动到墙前停止，边权为滚动距离。

使用最小堆维护当前最短距离的节点。

若终点被弹出，即得到最短距离。

复杂度分析：

时间复杂度：O(m _ n log(m _ n))。

空间复杂度：O(m * n)。

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int m = maze.length;
        int n = maze[0].length;
        int[][] dist = new int[m][n];
        for (int i = 0; i < m; i++) {
            Arrays.fill(dist[i], Integer.MAX_VALUE);
        }

        dist[start[0]][start[1]] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        pq.offer(new int[]{start[0], start[1], 0});

        int[] dr = {1, -1, 0, 0};
        int[] dc = {0, 0, 1, -1};

        while (!pq.isEmpty()) {
            int[] cur = pq.poll();
            int r = cur[0];
            int c = cur[1];
            int d = cur[2];

            if (d > dist[r][c]) {
                continue;
            }
            if (r == destination[0] && c == destination[1]) {
                return d;
            }

            for (int k = 0; k < 4; k++) {
                int nr = r;
                int nc = c;
                int steps = 0;
                while (nr + dr[k] >= 0 && nr + dr[k] < m && nc + dc[k] >= 0 && nc + dc[k] < n
                        && maze[nr + dr[k]][nc + dc[k]] == 0) {
                    nr += dr[k];
                    nc += dc[k];
                    steps++;
                }

                if (d + steps < dist[nr][nc]) {
                    dist[nr][nc] = d + steps;
                    pq.offer(new int[]{nr, nc, dist[nr][nc]});
                }
            }
        }

        return -1;
    }
}

import "container/heap"

type Node struct {
	r int
	c int
	d int
}

type MinHeap []Node

func (h MinHeap) Len() int { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].d < h[j].d }
func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Node)) }
func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func shortestDistance(maze [][]int, start []int, destination []int) int {
	m, n := len(maze), len(maze[0])
	dist := make([][]int, m)
	for i := 0; i < m; i++ {
		dist[i] = make([]int, n)
		for j := 0; j < n; j++ {
			dist[i][j] = 1 << 60
		}
	}

	dist[start[0]][start[1]] = 0
	h := &MinHeap{}
	heap.Init(h)
	heap.Push(h, Node{r: start[0], c: start[1], d: 0})
	dirs := [][2]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}

	for h.Len() > 0 {
		cur := heap.Pop(h).(Node)
		r, c, d := cur.r, cur.c, cur.d
		if d > dist[r][c] {
			continue
		}
		if r == destination[0] && c == destination[1] {
			return d
		}

		for _, dir := range dirs {
			nr, nc := r, c
			steps := 0
			for nr+dir[0] >= 0 && nr+dir[0] < m && nc+dir[1] >= 0 && nc+dir[1] < n && maze[nr+dir[0]][nc+dir[1]] == 0 {
				nr += dir[0]
				nc += dir[1]
				steps++
			}

			if d+steps < dist[nr][nc] {
				dist[nr][nc] = d + steps
				heap.Push(h, Node{r: nr, c: nc, d: d + steps})
			}
		}
	}

	return -1
}

相似题目

题目	难度	考察点
490. 迷宫	中等	BFS
499. 迷宫 III	困难	最短路
1091. 二进制矩阵中的最短路径	中等	BFS
773. 滑动谜题	困难	BFS
752. 打开转盘锁	中等	BFS

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/14817785