0499：迷宫 III（★★）

力扣第 499 题

题目

由空地和墙组成的迷宫中有一个球。球可以向上（u）下（d）左（l）右（r）四个方向滚动，但在遇到墙壁前不会停止滚动。当球停下时，可以选择下一个方向。迷宫中还有一个洞，当球运动经过洞时，就会掉进洞里。

给定球的起始位置，目的地和迷宫，找出让球以最短距离掉进洞里的路径。 距离的定义是球从起始位置（不包括）到目的地（包括）经过的空地个数。通过'u', 'd', 'l' 和 'r'输出球的移动方向。 由于可能有多条最短路径， 请输出字典序最小的路径。如果球无法进入洞，输出"impossible"。

迷宫由一个0和1的二维数组表示。 1表示墙壁，0表示空地。你可以假定迷宫的边缘都是墙壁。起始位置和目的地的坐标通过行号和列号给出。

示例1:

输入 1: 迷宫由以下二维数组表示

0 0 0 0 0
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 1 0 0 0

输入 2: 球的初始位置 (rowBall, colBall) = (4, 3)
输入 3: 洞的位置 (rowHole, colHole) = (0, 1)

输出: "lul"

解析: 有两条让球进洞的最短路径。
第一条路径是 左 -> 上 -> 左, 记为 "lul".
第二条路径是 上 -> 左, 记为 'ul'.
两条路径都具有最短距离6, 但'l' < 'u'，故第一条路径字典序更小。因此输出"lul"。

示例 2:

输入 1: 迷宫由以下二维数组表示

0 0 0 0 0
1 1 0 0 1
0 0 0 0 0
0 1 0 0 1
0 1 0 0 0

输入 2: 球的初始位置 (rowBall, colBall) = (4, 3)
输入 3: 洞的位置 (rowHole, colHole) = (3, 0)

输出: "impossible"

示例: 球无法到达洞。

注意:

1. 迷宫中只有一个球和一个目的地。
2. 球和洞都在空地上，且初始时它们不在同一位置。
3. 给定的迷宫不包括边界 (如图中的红色矩形), 但你可以假设迷宫的边缘都是墙壁。
4. 迷宫至少包括2块空地，行数和列数均不超过30。

分析

0505 进阶版:

• 遇到洞时中止滚动即可
• 除了距离，还要考虑路径的字典序，调整顺序一起入堆即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
	m, n = len(maze), len(maze[0])
	pq, d = [(0, '', *ball)], {}
	while pq:
		w, path, i, j = heappop(pq)
		if [i, j] == hole:
			return path
		if (i, j) in d:
			continue
		d[(i, j)] = w
		for dx, dy, p in [(-1, 0, 'u'), (1, 0, 'd'), (0, -1, 'l'), (0, 1, 'r')]:
			x, y, w2 = i, j, w
			while 0<=x+dx<m and 0<=y+dy<n and maze[x+dx][y+dy]==0:
				x, y, w2 = x+dx, y+dy, w2+1
				if [x, y] == hole:
					break
			if (x, y) not in d:
				heappush(pq, (w2, path+p, x, y))
	return 'impossible'

36 ms