> For the complete documentation index, see [llms.txt](https://netjimmy.gitbook.io/code-interview-note/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://netjimmy.gitbook.io/code-interview-note/bfs/the-maze.md).

# The Maze

## 490. The Maze

Given the ball's **start position**, the **destination** and the **maze**, determine whether the ball could stop at the destination.

![](/files/-MBAKEQ-jY73YhR1M5Wk)

```python
"""
利用while loop到達牆壁
只紀錄端點的情況
"""
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
    m, n = len(maze), len(maze[0])
    visited = set(tuple(start))
    q = [start]
    
    while q:
        pos = q.pop(0)
        
        for dy, dx in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            y = pos[0] + dy
            x = pos[1] + dx
            inloop = False
            
            while 0 <= y < m and 0 <= x < n and maze[y][x] == 0:
                inloop = True
                if pos == destination: return True
                y += dy
                x += dx
            
            # 記得退一步
            end = [y-dy, x-dx]
            if inloop and tuple(end) not in visited:
                q.append(end)
                visited.add(tuple(end))
                
    return False
```

## 505. The Maze II

Given the ball's **start position**, the **destination** and the **maze**, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of **empty spaces** traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.

![](/files/-MBAKgDp94k-6jcL8zag)

```python
def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
    m, n = len(maze), len(maze[0])
    dist = [[float('inf')] * n for _ in range(m)]
    dist[start[0]][start[1]] = 0
    q = [(start[0], start[1], 0)]
    d = destination
    
    while q:
        p1, p2, step = q.pop(0)
        for dy, dx in ((0, 1), (1, 0), (0, -1), (-1, 0)):
            s = step + 1
            y = p1 + dy
            x = p2 + dx
            
            found = False
            inloop = False
            
            while 0 <= y < m and 0 <= x < n and maze[y][x] == 0:
                inloop = True
                if (y, x) == d and s < dist[y][x]:
                    dist[y][x] = [y, x]
                    found = True
                    break       
                s += 1
                y += dy
                x += dx
                
            # 記得退一步
            y, x = y-dy, x-dx
            s -= 1

            if inloop and not found and s < dist[y][x]:
                dist[y][x] = s
                q.append((y, x, s))

    return dist[d[0]][d[1]] if dist[d[0]][d[1]] != float('inf') else -1
```

499\. The Maze III

Given the **ball position**, the **hole position** and the **maze**, find out how the ball could drop into the hole by moving the **shortest distance**. The distance is defined by the number of **empty spaces** traveled by the ball from the start position (excluded) to the hole (included). Output the moving **directions** by using 'u', 'd', 'l' and 'r'. Since there could be several different shortest ways, you should output the **lexicographically smallest** way. If the ball cannot reach the hole, output "impossible".

![](/files/-MBAMHJm4Kzt4ONK_1Pk)

```python
 def findShortestWay(self, maze: List[List[int]], ball: List[int], hole: List[int]) -> str:
    m, n = len(maze), len(maze[0])
    dist = [[(float('inf'), [])] * n for _ in range(m)]
    q = [(ball[0], ball[1], 0, [''])]
    dirs = {0:'r', 1:'d', 2:'l', 3:'u'}
    
    while q:
        p1, p2, step, routes = q.pop(0)
        for i, (dy, dx) in enumerate(((0, 1), (1, 0), (0, -1), (-1, 0))):
            s = step+1
            y = p1+dy
            x = p2+dx
            new_routes = [r+dirs[i] for r in routes]
            found = False
            inloop = False
            while 0 <= y < m and 0 <= x < n and maze[y][x] == 0:
                inloop = True
                if [y, x] == hole:
                    if s == dist[y][x][0]:
                        dist[y][x] = (s, dist[y][x][1] + new_routes)
                    elif s < dist[y][x][0]:
                        dist[y][x] = (s, new_routes)
                    found = True
                    break
                s += 1
                y += dy
                x += dx
                     
            # 記得退一步
            y, x = y-dy, x-dx
            s -= 1
            if inloop and not found and s <= dist[y][x][0]:
                if s == dist[y][x][0]:
                    dist[y][x] = (s, dist[y][x][1] + new_routes)
                elif s < dist[y][x][0]:
                    dist[y][x] = (s, new_routes)
                q.append((y, x, s, new_routes))

    if dist[hole[0]][hole[1]][0] == float('inf'): return 'impossible'
    return sorted(dist[hole[0]][hole[1]][1])[0] 
```