The Maze II

Updated on 04 July, 2025
The Maze II header image

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

  • Java
java
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]]});
                }
            }
        }
    }
}

The provided Java solution deals with finding the minimum distance in a maze from a start position to an end position using a modified Dijkstra's algorithm. Here's a summary of how the solution is structured and its execution logic:

  • Initialization of Distance Array:

    • A 2D array named dist is initialized with maximum integer values, representing the distance from the start position to each cell in the maze. The distance at the start position is set to 0.
  • Dijkstra's Algorithm Implementation:

    • A priority queue (min-heap) is employed to ensure cells with the smallest tentative distance are processed first.
    • The queue begins with the start position. The program continually polls this queue to get the next cell to process based on the smallest distance.
    • For each cell processed, the algorithm computes the possible moves in all four cardinal directions (up, down, left, right). The cell continues moving in a direction until an obstacle (1) in the maze or the boundary is encountered.
    • On reaching an accessible cell, the code checks if a shorter path to this position has been found (compared to previously recorded in dist), and if so, it updates the distance and adds the new position to the queue.
  • End Result Calculation:

    • The final minimum distance to the end position is retrieved from the dist array. If it remains the maximum integer value (indicative of the end position being unreachable), the method returns -1, indicating such.
  • Complexity and Efficiency:

    • The use of a 2D array for distance tracking and a priority queue for processing positions in the order of distance ensures that each cell is processed in an efficient manner, especially crucial for larger mazes.

This solution elegantly handles complexities associated with unidirectional and potential infinite looping paths in the maze by implementing boundary checks and obstacle detection, effectively managing the complexities of pathfinding in a maze environment with obstacles.

Comments

No comments yet.