LeetCode Solutions Blog

The Maze III

Number: 499

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Given a maze where empty spaces are 0 and walls are 1, a ball rolls one direction until hitting a wall. There is a single hole in the maze. Starting from the ball’s position, determine the instruction string (using 'u', 'd', 'l', 'r') by which the ball can drop into the hole following the shortest distance. If more than one shortest path exists, return the lexicographically smallest string. If the ball cannot drop into the hole at all, return "impossible".

Key Insights

The ball rolls continuously until hitting a wall or falling into the hole.
A shortest path search is needed based on rolling distance (each step counts when passing an empty cell).
Dijkstra’s algorithm (or a modified BFS with a priority queue) is appropriate since we need to consider distance and lexicographic order.
When expanding moves, simulate the roll until the ball stops — if a hole is passed en route, use that stopping point.
Track the best (distance, path) for each cell to avoid redundant work.

Space and Time Complexity

Time Complexity: O(mn log(mn)) where m and n are the maze dimensions
Space Complexity: O(mn)

Solution

We use a Dijkstra-like approach with a priority queue containing tuples of (distance, path, row, col). The priority queue is ordered by distance first and then by the instruction string lexicographically. For each cell, simulate rolling in each possible direction (up, down, left, right; iterated in alphabetical order so that the lexicographical property is maintained) until the ball stops. If the ball encounters the hole during rolling, treat that as a valid stop immediately. For every new stopping cell, if a shorter distance or lexicographically smaller path is found, update the record and add the new state to the priority queue. If you reach the hole, return the corresponding path string. If no solution is found when the queue is empty, return "impossible".

Code Solutions

import heapq

def findShortestWay(maze, ball, hole):
    m, n = len(maze), len(maze[0])
    # Directions: sorted lexicographically as 'd' < 'l' < 'r' < 'u'
    # since ASCII: d(100), l(108), r(114), u(117)
    directions = [('d', 1, 0), ('l', 0, -1), ('r', 0, 1), ('u', -1, 0)]
    
    # Initialize distance and path record, fill with (infty, "")
    dist = [[float('inf')] * n for _ in range(m)]
    pathRecord = [[""] * n for _ in range(m)]
    
    # Priority queue stores tuples: (distance, path, row, col)
    heap = [(0, "", ball[0], ball[1])]
    dist[ball[0]][ball[1]] = 0
    
    while heap:
        curDist, curPath, x, y = heapq.heappop(heap)
        # If we pop a state for the hole then return result.
        if [x, y] == hole:
            return curPath
        # If we have a larger distance than already recorded, continue.
        if curDist > dist[x][y]:
            continue
        # Explore all four directions
        for d, dx, dy in directions:
            nx, ny = x, y
            steps = 0
            # Roll the ball until hitting a wall or passing through the hole.
            # Check if ball goes through the hole during rolling.
            while 0 <= nx + dx < m and 0 <= ny + dy < n and maze[nx + dx][ny + dy] == 0:
                nx += dx
                ny += dy
                steps += 1
                if [nx, ny] == hole:
                    break
            newDist = curDist + steps
            newPath = curPath + d
            # If we found a shorter route or equal distance but lexicographically smaller route.
            if newDist < dist[nx][ny] or (newDist == dist[nx][ny] and newPath < pathRecord[nx][ny]):
                dist[nx][ny] = newDist
                pathRecord[nx][ny] = newPath
                heapq.heappush(heap, (newDist, newPath, nx, ny))
    return "impossible"

# Example usage:
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]
print(findShortestWay(maze, ball, hole))  # Expected output: "lul"