> ## Documentation Index
> Fetch the complete documentation index at: https://leetcode-py.wisl.dev/llms.txt
> Use this file to discover all available pages before exploring further.

> ## Agent Instructions
> leetcode-py is a Python LeetCode practice environment generator with one CLI: lcpy. It is not a service or platform.
> Each problem is a directory under leetcode/ with README.md, solution.py, test_solution.py, helpers.py, and playground.ipynb. lcpy gen creates them from JSON templates bundled with the package.
> Examples are backed by tests; copy them verbatim.

# The Maze III Python Solution with Tests

> Tested Python solution for LeetCode 499 with 11 pytest cases. Generate a practice environment with lcpy.

LeetCode 499, [Hard](/catalog/hard). Topics: [Depth-First Search](/catalog/topics/depth-first-search), [Breadth-First Search](/catalog/topics/breadth-first-search), [Graph](/catalog/topics/graph), [Array](/catalog/topics/array), [String](/catalog/topics/string), [Matrix](/catalog/topics/matrix), [Shortest Path](/catalog/topics/shortest-path), Dijkstra, [Heap (Priority Queue)](/catalog/topics/heap-priority-queue). [View on LeetCode](https://leetcode.com/problems/the-maze-iii/description/).

Generate this problem as a practice environment: tested reference solution, 11 [parametrized pytest cases](/practice/testing), and a playground notebook:

```bash theme={"theme":{"light":"github-light","dark":"github-dark"}}
lcpy gen -n 499   # by problem number
lcpy gen -s the_maze_iii   # by problem name
```

## Problem

There is a ball in a `maze` with empty spaces (represented as `0`) and walls (represented as `1`). The ball can go through the empty spaces by rolling **up, down, left or right**, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction (must be different from last chosen direction). There is also a hole in this maze. The ball will drop into the hole if it rolls onto the hole.

Given the `m x n` `maze`, the ball's position `ball` and the hole's position `hole`, where `ball = [ball_row, ball_col]` and `hole = [hole_row, hole_col]`, return a string `instructions` of all the instructions that the ball should follow to drop in the hole with the **shortest distance** possible. If there are multiple valid instructions, return the **lexicographically minimum** one. If the ball can't drop in the hole, return `"impossible"`.

If there is a way for the ball to drop in the hole, the answer `instructions` should contain the characters `'u'` (i.e. up), `'d'` (i.e. down), `'l'` (i.e. left), and `'r'` (i.e. right).

The **distance** is the number of **empty spaces** traveled by the ball from the start position (excluded) to the destination (included).

You may assume that **the borders of the maze are all walls** (see examples).

### Examples

![Example 1](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/0400-0499/0499.The%20Maze%20III/images/maze3-1-grid.jpg)

```
Input: maze = [[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]], ball = [4,3], hole = [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](https://fastly.jsdelivr.net/gh/doocs/leetcode@main/solution/0400-0499/0499.The%20Maze%20III/images/maze3-2-grid.jpg)

```
Input: maze = [[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]], ball = [4,3], hole = [3,0]
Output: "impossible"
Explanation: The ball cannot reach the hole.
```

```
Input: maze = [[0,0,0,0,0,0,0],[0,0,1,0,0,1,0],[0,0,0,0,1,0,0],[0,0,0,0,0,0,1]], ball = [0,4], hole = [3,5]
Output: "dldr"
```

### Constraints

* `m == maze.length`
* `n == maze[i].length`
* `1 <= m, n <= 100`
* `maze[i][j]` is `0` or `1`.
* `ball.length == 2`
* `hole.length == 2`
* `0 <= ball_row, hole_row <= m`
* `0 <= ball_col, hole_col <= n`
* Both the ball and the hole exist in an empty space, and they will not be in the same position initially.
* The maze contains **at least 2 empty spaces**.

## Solution

Reference implementation from [solution.py on GitHub](https://github.com/wislertt/leetcode-py/blob/main/leetcode/the_maze_iii/solution.py), full suite in [test\_solution.py](https://github.com/wislertt/leetcode-py/blob/main/leetcode/the_maze_iii/test_solution.py):

```python theme={"theme":{"light":"github-light","dark":"github-dark"}}
import heapq


class Solution:
    # Time: O(m * n * max(m, n) * log(m * n))
    # Space: O(m * n)
    def find_shortest_way(self, maze: list[list[int]], ball: list[int], hole: list[int]) -> str:
        m, n = len(maze), len(maze[0])
        dirs = (("d", (1, 0)), ("l", (0, -1)), ("r", (0, 1)), ("u", (-1, 0)))
        goal = (hole[0], hole[1])
        best: dict[tuple[int, int], tuple[int, str]] = {(ball[0], ball[1]): (0, "")}
        heap = [(0, "", ball[0], ball[1])]
        while heap:
            dist, path, r, c = heapq.heappop(heap)
            if (r, c) == goal:
                return path
            if best.get((r, c)) != (dist, path):
                continue
            for ch, (dr, dc) in dirs:
                nr, nc, steps = r, c, 0
                while 0 <= nr + dr < m and 0 <= nc + dc < n and maze[nr + dr][nc + dc] == 0:
                    nr += dr
                    nc += dc
                    steps += 1
                    if (nr, nc) == goal:
                        break
                cand = (dist + steps, path + ch)
                if (nr, nc) not in best or cand < best[(nr, nc)]:
                    best[(nr, nc)] = cand
                    heapq.heappush(heap, (cand[0], cand[1], nr, nc))
        return "impossible"
```

## Complexity

| Time | Space |
| - | - |
| O(m \* n \* max(m, n) \* log(m \* n)) | O(m \* n) |

## Tags

[NeetCode All](/catalog/neetcode).


This documentation is built and hosted on [Mintlify](https://mintlify.com), a developer documentation platform.