The Maze III

A rolling ball must reach a hole in the maze. Return the shortest path string, and break ties lexicographically when multiple shortest paths exist. Pattern focus: Min-heap. Combine distance ordering with path-string tie breaking.

Input Format

maze = grid, ball = starting coordinate, hole = target coordinate

Output Format

shortest path string or impossible

Constraints

  • 1 <= rows, cols <= 30
  • maze contains 0 for open and 1 for wall

Examples

Example 1:

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:

This is the standard lexicographic tie-breaking example.

Example 2:

Input:

maze = [[0,0],[0,0]]
ball = [0,0]
hole = [1,1]

Output:

impossible

Explanation:

The ball cannot stop at the hole.

Example 3:

Input:

maze = [[0,0,0],[0,0,0],[0,0,0]]
ball = [2,0]
hole = [0,0]

Output:

u

Explanation:

The ball can roll straight up to the hole.

Loading...
The Maze III - Shortest Path DSA Problem