The Maze II

Problem Statement

In this problem, we are given a rectangular maze where each cell either represents an empty space (0) or a wall (1). The maze also defines a start and destination position for a ball. The goal is for the ball to reach the destination by rolling through empty spaces in one of the four cardinal directions: up, down, left, or right. The ball cannot stop mid-roll unless it hits a wall; once it hits a wall, it can immediately pick a new direction to roll in.

The task is to determine the shortest path for the ball to travel from its starting position to the destination, in terms of the number of empty spaces crossed. The ball must stop exactly at the destination for a valid path. If a valid path does not exist, the function should return -1. The boundaries of the maze are assumed to be walls, and the distance counted excludes the start position but includes the destination.

Examples

Example 1

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]

Output:

12

Explanation:

One possible way is : left -> down -> left -> down -> right -> down -> right.
The length of the path is 1 + 1 + 3 + 1 + 2 + 2 + 2 = 12.

Example 2

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 = [3,2]

Output:

-1

Explanation:

There is no way for the ball to stop at the destination. Notice that you can pass through the destination but you cannot stop there.

Example 3

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]], start = [4,3], destination = [0,1]

Output:

-1

Constraints

• m == maze.length
• n == maze[i].length
• 1 <= m, n <= 100
• maze[i][j] is 0 or 1.
• start.length == 2
• destination.length == 2
• 0 <= startrow, destinationrow < m
• 0 <= startcol, destinationcol < n
• Both the ball and the destination exist in an empty space, and they will not be in the same position initially.
• The maze contains at least 2 empty spaces.

Approach and Intuition

1. Use Breadth-First Search (BFS) for finding the shortest path:

   • We can visualize each possible stop (each cell in the maze the ball can reach after hitting a wall) as a node in a graph. The ball's transitions from one stop to another, when it rolls and hits a wall, form the edges between these nodes.
   • Use a BFS algorithm to traverse this "graph". This involves treating each stop as a node and queuing each new stop the ball can roll to from there.

2. Nodes and States:

   • Each BFS node will not only contain the ball's current position but also the accumulated distance from the start position.

3. Initialize:

   • Start BFS with the initial position of the ball and a distance of 0. This position will be treated as the root node of our BFS.

4. Move and Explore:

   • From each node, move the ball in all four possible directions until a wall stops it.
   • For every stop, calculate the total distance traveled and check if this stop has been reached before with a shorter distance; if not, add it to the BFS queue.

5. Reaching the Destination:

   • If the ball stops exactly on the destination cell, examine the distance. Capture and return the shortest one found.

6. Consider Edge Cases:

   • If the BFS completes and the destination was never reached or the ball could not stop exactly at the destination, return -1.

Through these systematic steps, the algorithm effectively finds the shortest possible route for the ball using BFS to traverse the maze while considering all possible paths the ball can take in its rolling constraints.

Solutions

public class Solution {
    public int findMinDistance(int[][] labyrinth, int[] startPosition, int[] endPosition) {
        int[][] dist = new int[labyrinth.length][labyrinth[0].length];
        for (int[] row: dist)
            Arrays.fill(row, Integer.MAX_VALUE);
        dist[startPosition[0]][startPosition[1]] = 0;
        executeDijkstra(labyrinth, startPosition, dist);
        return dist[endPosition[0]][endPosition[1]] == Integer.MAX_VALUE ? -1 : dist[endPosition[0]][endPosition[1]];
    }
    
    public void executeDijkstra(int[][] labyrinth, int[] start, int[][] dist) {
        int[][] directions={{0,1},{0,-1},{-1,0},{1,0}};
        PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[2] - b[2]);
        minHeap.offer(new int[]{start[0], start[1], 0});
        while (!minHeap.isEmpty()) {
            int[] current = minHeap.poll();
            if(dist[current[0]][current[1]] < current[2])
                continue;
            for (int[] direction: directions) {
                int x = current[0] + direction[0];
                int y = current[1] + direction[1];
                int moves = 0;
                while (x >= 0 && y >= 0 && x < labyrinth.length && y < labyrinth[0].length && labyrinth[x][y] == 0) {
                    x += direction[0];
                    y += direction[1];
                    moves++;
                }
                if (dist[current[0]][current[1]] + moves < dist[x - direction[0]][y - direction[1]]) {
                    dist[x - direction[0]][y - direction[1]] = dist[current[0]][current[1]] + moves;
                    minHeap.offer(new int[]{x - direction[0], y - direction[1], dist[x - direction[0]][y - direction[1]]});
                }
            }
        }
    }
}