## 题目描述：

LeetCode 499. The Maze II

There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling up (u), down (d), left (l) or right (r), but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction. There is also a hole in this maze. The ball will drop into the hole if it rolls on to the hole.

Given the ball position, the hole position and the maze, your job is to find out how the ball could drop into the hole by moving shortest distance in the maze. The distance is defined by the number of empty spaces the ball go through from the start position (exclude) to the hole (include). Output the moving directions by using 'u', 'd', 'l' and 'r'. Since there may have several different shortest ways, you should output the lexicographically smallest way. If the ball cannot reach the hole, output "impossible".

The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The ball and hole coordinates are represented by row and column indexes.

Example 1

```Input 1: a maze represented by a 2D array

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

Input 2: ball coordinate (rowBall, colBall) = (4, 3)
Input 3: hole coordinate (rowHole, colHole) = (0, 1)

Output: "lul"
Explanation: There are two shortest ways for the ball to drop into the hole.
The first way is left -> up -> left, represented by "lul".
The second way is up -> left, represented by 'ul'.
Both ways have shortest distance 6, but the first way is lexicographically smaller because 'l' < 'u'. So the output is "lul". ```

Example 2

```Input 1: a maze represented by a 2D array

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

Input 2: ball coordinate (rowBall, colBall) = (4, 3)
Input 3: hole coordinate (rowHole, colHole) = (3, 0)
Output: "impossible"
Explanation: The ball cannot reach the hole. ```

Note:

1. There are only one ball and one hole in the maze.
2. The ball and hole will only exist in the empty space, and they will not at the same position initially.
3. The given maze doesn't contain border (like the red rectangle in the example pictures), but you should assume the border of the maze are all walls.
4. The maze contains at least 2 empty spaces, and the length and width of the maze won't exceed 30.

## 题目大意：

1. 球和洞各只有1个。
2. 球和洞只存在于空地上，并且初始位置不同。
3. 给定的迷宫不包含边界，但迷宫四周都是墙壁。
4. 迷宫至少包含两个空地，并且迷宫的长度和宽度不超过30。

## 解题思路：

```首先预处理迷宫maze中各点坐标向四个方向运动最终可以达到的坐标，用数组dmap记录。

## Python代码：

``````class Solution(object):
def findShortestWay(self, maze, ball, hole):
"""
:type maze: List[List[int]]
:type ball: List[int]
:type hole: List[int]
:rtype: str
"""
ball, hole = tuple(ball), tuple(hole)
dmap = collections.defaultdict(lambda: collections.defaultdict(int))
w, h = len(maze), len(maze)
for dir in 'dlru': dmap[hole][dir] = hole
for x in range(w):
for y in range(h):
if maze[x][y] or (x, y) == hole: continue
dmap[(x, y)]['u'] = dmap[(x - 1, y)]['u'] if x > 0 and dmap[(x - 1, y)]['u'] else (x, y)
dmap[(x, y)]['l'] = dmap[(x, y - 1)]['l'] if y > 0 and dmap[(x, y - 1)]['l'] else (x, y)
for x in range(w - 1, -1, -1):
for y in range(h - 1, -1, -1):
if maze[x][y] or (x, y) == hole: continue
dmap[(x, y)]['d'] = dmap[(x + 1, y)]['d'] if x < w - 1 and dmap[(x + 1, y)]['d'] else (x, y)
dmap[(x, y)]['r'] = dmap[(x, y + 1)]['r'] if y < h - 1 and dmap[(x, y + 1)]['r'] else (x, y)
bmap = {ball : (0, '')}
distance = lambda pa, pb: abs(pa - pb) + abs(pa - pb)
queue = collections.deque([(ball, 0, '')])
while queue:
front, dist, path = queue.popleft()
for dir in 'dlru':
if dir not in dmap[front]: continue
np = dmap[front][dir]
ndist = dist + distance(front, np)
npath = path + dir
if np not in bmap or (ndist, npath) < bmap[np]:
bmap[np] = (ndist, npath)
queue.append((np, ndist, npath))
return bmap[hole] if hole in bmap else 'impossible'
``````

## Python代码：

``````class Solution(object):
def findShortestWay(self, maze, ball, hole):
"""
:type maze: List[List[int]]
:type ball: List[int]
:type hole: List[int]
:rtype: str
"""
ball, hole = tuple(ball), tuple(hole)
dmap = collections.defaultdict(lambda: collections.defaultdict(int))
w, h = len(maze), len(maze)
for dir in 'dlru': dmap[hole][dir] = hole
for x in range(w):
for y in range(h):
if maze[x][y] or (x, y) == hole: continue
dmap[(x, y)]['u'] = dmap[(x - 1, y)]['u'] if x > 0 and dmap[(x - 1, y)]['u'] else (x, y)
dmap[(x, y)]['l'] = dmap[(x, y - 1)]['l'] if y > 0 and dmap[(x, y - 1)]['l'] else (x, y)
for x in range(w - 1, -1, -1):
for y in range(h - 1, -1, -1):
if maze[x][y] or (x, y) == hole: continue
dmap[(x, y)]['d'] = dmap[(x + 1, y)]['d'] if x < w - 1 and dmap[(x + 1, y)]['d'] else (x, y)
dmap[(x, y)]['r'] = dmap[(x, y + 1)]['r'] if y < h - 1 and dmap[(x, y + 1)]['r'] else (x, y)
bmap = {ball : (0, '', ball)}
vset = set()
distance = lambda pa, pb: abs(pa - pb) + abs(pa - pb)
while bmap:
dist, path, p = min(bmap.values())
if p == hole: return path
del bmap[p]
vset.add(p)
for dir in 'dlru':
if dir not in dmap[p]: continue
np = dmap[p][dir]
ndist = dist + distance(p, np)
npath = path + dir
if np not in vset and (np not in bmap or (ndist, npath, np) < bmap[np]):
bmap[np] = (ndist, npath, np)
return 'impossible'
``````

Pingbacks已关闭。