Problem Description

You are given a maze represented by a 2D grid, where 0 indicates an empty space and 1 indicates a wall. The maze has a ball that can roll in four directions (up, down, left, right). However, the ball will keep rolling in a chosen direction until it hits a wall or the maze boundary—it cannot stop in the middle of an empty space.

Given:

• maze: a 2D list of integers (0 for open, 1 for wall)
• start: a list of two integers representing the starting coordinates [row, col]
• destination: a list of two integers representing the target coordinates [row, col]

Constraints:

• The ball cannot change direction until it hits a wall.
• It may not stop in the middle of an open area.
• There may be multiple possible paths; find the shortest one.
• Do not revisit the same cell with a higher or equal number of steps.

Thought Process

At first glance, this seems like a standard shortest path problem in a grid, similar to BFS (Breadth-First Search). However, the twist is that the ball rolls until it hits a wall, so you cannot simply move one cell at a time.

A brute-force approach would be to try all possible paths, but this would be very inefficient, especially since the ball can travel a long way in a single direction. Instead, we need to optimize by:

• Tracking the minimum distance to each cell and not revisiting a cell with a longer path.
• Simulating the rolling process efficiently, only stopping when the ball hits a wall or boundary.
• Using a priority queue (for Dijkstra's algorithm) to always expand the shortest current path, since the cost to reach each cell can vary.

Solution Approach

To solve the problem efficiently, we use Dijkstra's algorithm because:

• The cost to reach each cell (number of steps) can differ depending on the path taken.
• We want the shortest path, not just any path.

1. Initialize Data Structures:
   • Create a 2D array distance to store the shortest distance to each cell, initialized to infinity.
   • Use a min-heap (priority queue) to always process the cell with the smallest current distance.
2. Start from the Initial Position:
   • Push the starting position and distance (0) into the heap.
   • Set the distance to the start cell as 0.
3. Expand Paths:
   • While the heap is not empty, pop the cell with the smallest distance.
   • For each direction (up, down, left, right):
   • Roll the ball in that direction until it hits a wall or boundary, counting the number of steps taken.
   • If the new position offers a shorter path than previously recorded, update the distance array and add it to the heap.
4. Check for the Destination:
   • If the destination cell is reached, return the distance.
   • If the heap is exhausted, return -1 (unreachable).

This approach ensures we always find the shortest path due to the properties of Dijkstra's algorithm.

Example Walkthrough

Input:
maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]]
start = [0,4]
destination = [4,4]

1. Start at (0,4) with distance 0.
2. Try all four directions:
   • Down: Ball rolls to (4,4) in 4 steps (since no wall in that column).
   • Left: Ball stops at (0,3) as (0,2) is a wall.
   • Up and Right: Out of bounds immediately.
3. Update distance for (4,4) to 4 and (0,3) to 1. Both are added to the queue.
4. Next, process (0,3):
   • Try rolling further left: stops at (0,0).
   • Other directions either hit walls or revisit cells with no shorter path.
5. Continue expanding until the destination (4,4) is reached with the minimal steps (12 in this example).

The algorithm always chooses the cell with the currently smallest distance, ensuring the shortest path is found.

Time and Space Complexity

• Brute-force:
  • Could be exponential in the number of empty cells, as it may revisit the same cell with different paths.
• Optimized (Dijkstra's Algorithm):
  • Time Complexity: O(m * n * log(mn)) where m and n are the maze dimensions. Each cell can be pushed into the heap at most once per direction, and heap operations are logarithmic.
  • Space Complexity: O(m * n) for the distance array and the heap.

Summary

The key insight is to treat the maze as a weighted graph where each roll to a wall is a single edge, and to use Dijkstra's algorithm to always expand the shortest path first. By simulating the rolling movement and updating distances only when a shorter path is found, we efficiently find the shortest route to the destination. This strategy is both elegant and optimal for the problem's unique movement constraints.

Code Implementation

import heapq

class Solution:
    def shortestDistance(self, maze, start, destination):
        m, n = len(maze), len(maze[0])
        distance = [[float('inf')] * n for _ in range(m)]
        heap = []
        heapq.heappush(heap, (0, start[0], start[1]))
        distance[start[0]][start[1]] = 0
        dirs = [(-1,0), (1,0), (0,-1), (0,1)]
        
        while heap:
            dist, x, y = heapq.heappop(heap)
            if [x, y] == destination:
                return dist
            for dx, dy in dirs:
                nx, ny, steps = x, y, 0
                # Roll the ball until it hits a wall
                while 0 <= nx+dx < m and 0 <= ny+dy < n and maze[nx+dx][ny+dy] == 0:
                    nx += dx
                    ny += dy
                    steps += 1
                if distance[nx][ny] > dist + steps:
                    distance[nx][ny] = dist + steps
                    heapq.heappush(heap, (distance[nx][ny], nx, ny))
        return -1
      

#include <vector>
#include <queue>
#include <climits>
using namespace std;

class Solution {
public:
    int shortestDistance(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<int>> dist(m, vector<int>(n, INT_MAX));
        priority_queue<pair<int, pair<int,int>>, vector<pair<int, pair<int,int>>>, greater<pair<int, pair<int,int>>>> heap;
        vector<pair<int,int>> dirs{{-1,0},{1,0},{0,-1},{0,1}};
        heap.push({0, {start[0], start[1]}});
        dist[start[0]][start[1]] = 0;
        
        while (!heap.empty()) {
            auto curr = heap.top(); heap.pop();
            int d = curr.first, x = curr.second.first, y = curr.second.second;
            if (x == destination[0] && y == destination[1]) return d;
            for (auto dir : dirs) {
                int nx = x, ny = y, steps = 0;
                while (nx + dir.first >= 0 && nx + dir.first < m && ny + dir.second >= 0 && ny + dir.second < n && maze[nx + dir.first][ny + dir.second] == 0) {
                    nx += dir.first;
                    ny += dir.second;
                    steps++;
                }
                if (dist[nx][ny] > d + steps) {
                    dist[nx][ny] = d + steps;
                    heap.push({dist[nx][ny], {nx, ny}});
                }
            }
        }
        return -1;
    }
};
      

import java.util.*;

public class Solution {
    public int shortestDistance(int[][] maze, int[] start, int[] destination) {
        int m = maze.length, n = maze[0].length;
        int[][] dist = new int[m][n];
        for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE);
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        heap.offer(new int[]{0, start[0], start[1]});
        dist[start[0]][start[1]] = 0;
        int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
        
        while (!heap.isEmpty()) {
            int[] curr = heap.poll();
            int d = curr[0], x = curr[1], y = curr[2];
            if (x == destination[0] && y == destination[1]) return d;
            for (int[] dir : dirs) {
                int nx = x, ny = y, steps = 0;
                while (nx + dir[0] >= 0 && nx + dir[0] < m && ny + dir[1] >= 0 && ny + dir[1] < n && maze[nx + dir[0]][ny + dir[1]] == 0) {
                    nx += dir[0];
                    ny += dir[1];
                    steps++;
                }
                if (dist[nx][ny] > d + steps) {
                    dist[nx][ny] = d + steps;
                    heap.offer(new int[]{dist[nx][ny], nx, ny});
                }
            }
        }
        return -1;
    }
}
      

/**
 * @param {number[][]} maze
 * @param {number[]} start
 * @param {number[]} destination
 * @return {number}
 */
var shortestDistance = function(maze, start, destination) {
    const m = maze.length, n = maze[0].length;
    const dist = Array.from({length: m}, () => Array(n).fill(Infinity));
    const heap = [[0, start[0], start[1]]];
    dist[start[0]][start[1]] = 0;
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    
    while (heap.length > 0) {
        heap.sort((a, b) => a[0] - b[0]);
        const [d, x, y] = heap.shift();
        if (x === destination[0] && y === destination[1]) return d;
        for (const [dx, dy] of dirs) {
            let nx = x, ny = y, steps = 0;
            while (nx + dx >= 0 && nx + dx < m && ny + dy >= 0 && ny + dy < n && maze[nx + dx][ny + dy] === 0) {
                nx += dx;
                ny += dy;
                steps++;
            }
            if (dist[nx][ny] > d + steps) {
                dist[nx][ny] = d + steps;
                heap.push([dist[nx][ny], nx, ny]);
            }
        }
    }
    return -1;
};