The Maze

Updated on 04 July, 2025
The Maze header image

Problem Statement

In this problem, there is a ball within a maze that includes empty spaces and walls. Empty spaces allow the movement of the ball and are represented by 0, while walls, represented by 1, restrict the movement. The ball, when moved in any of the four cardinal directions (up, down, left, or right), continues in that direction until it hits a wall. Once it encounters a wall, it stops and can then be directed again along any of the four possible directions.

The maze itself is defined as a m x n grid, and the ball's starting and intended destination positions are given as [startrow, startcol] and [destinationrow, destinationcol], respectively. The goal is to determine if it is possible for the ball to stop exactly at the destination point. If the ball can be navigated to stop at the destination, the function should return true; otherwise, it should return false. The outer boundaries of the maze are all treated as walls, which can affect the movement strategies for solving the maze.

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:

true

Explanation:

One possible way is : left -> down -> left -> down -> right -> down -> right.

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:

false

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:

false

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

The key challenge in this problem is navigating the ball from the start position to the destination such that the ball stops precisely at the destination. To effectively tackle this challenge, consider the following approach:

  1. Graph Representation and BFS/DFS Usage: The maze can be seen as a graph where every cell is a node and movement directions (up, down, left, right) that don't immediately hit a wall can be considered edges. Breadth-First Search (BFS) or Depth-First Search (DFS) can efficiently explore this graph.

  2. Mark Visited Paths: As the ball moves through the maze, marking cells as visited is crucial, especially to denote the stopping points after a ball starts rolling in one direction. This will prevent the algorithm from infinite loops and reduce redundant calculations.

  3. Simulate Movement: For each direction (up, down, left, right), simulate the movement of the ball until it hits a wall. Once a halt is achieved, record the position, then recursively or iteratively explore the next possible movements.

  4. Check for Destination: After every move simulation, check if the stopping point of the ball matches the destination coordinates. If at any point the destination is achieved with the ball halting there, return true.

  5. Edge Cases Handling: Edge cases include scenarios where the start or destination is immediately next to a wall, or complex mazes where movement paths are intricately intertwined or minimal due to dense wall placements.

In essence, the problem is about effectively maneuvering through a space with constraints, utilizing graph traversal techniques to explore potential pathways to a target node (the destination), and ensuring that the end conditions (stopping at the destination) are satisfied.

Solutions

  • C++
cpp
class Solution {
public:
    bool canReach(vector<vector<int>>& grid, vector<int>& start, vector<int>& end) {
        int rows = grid.size();
        int cols = grid[0].size();
        vector<vector<bool>> visited(rows, vector<bool>(cols, false));
        vector<int> deltaX{0, 1, 0, -1};
        vector<int> deltaY{-1, 0, 1, 0};
    
        queue<vector<int>> queue;
        queue.push(start);
        visited[start[0]][start[1]] = true;
    
        while (!queue.empty()) {
            vector<int> current = queue.front();
            queue.pop();
            if (current[0] == end[0] && current[1] == end[1]) {
                return true;
            }
    
            for (int i = 0; i < 4; i++) {
                int x = current[0];
                int y = current[1];
              
                while (x >= 0 && x < rows && y >= 0 && y < cols && grid[x][y] == 0) {
                    x += deltaX[i];
                    y += deltaY[i];
                }
              
                x -= deltaX[i];
                y -= deltaY[i];
                if (!visited[x][y]) {
                    queue.push({x, y});
                    visited[x][y] = true;
                }
            }
        }
        return false;
    }
};

The Maze problem involves determining whether there is a path from a start point to an endpoint in a 2D grid represented by 0s and 1s, where 0 indicates an open path and 1 indicates a wall.

  • You can solve this problem using a Breadth-First Search (BFS) approach:

    • Initialize a queue and add the start position to it. The visited 2D vector keeps track of visited nodes to avoid revisiting them.
    • While the queue is not empty, dequeue the front element. If this element is the end position, return true to indicate that the endpoint is reachable.
    • For each possible move (up, down, left, and right), calculate the next position until hitting a wall or the boundary of the grid. Then move back one step to the last valid position.
    • If this new position has not been visited, mark it as visited, and enqueue it for further exploration.
    • If you exhaust all possibilities and do not find the end position, return false as it is not reachable.

This solution efficiently explores the grid by only visiting each potential path once and backtracking only when necessary. Continue optimizing based on the specific constraints and sizes of the input grid.

  • Java
java
class MazeSolver {
    public boolean canReach(int[][] maze, int[] start, int[] end) {
        // Getting maze dimensions
        int rows = maze.length;
        int cols = maze[0].length;
            
        // Visited cells tracker
        boolean[][] visited = new boolean[rows][cols];
            
        // Directions arrays
        int[] deltaX = {0, 1, 0, -1};
        int[] deltaY = {-1, 0, 1, 0};
    
        // Queue for breadth-first search
        Queue<int[]> bfsQueue = new LinkedList<>();
        bfsQueue.offer(start);
        visited[start[0]][start[1]] = true;
    
        while (!bfsQueue.isEmpty()) {
            int[] current = bfsQueue.poll();
            if (current[0] == end[0] && current[1] == end[1]) {
                return true;
            }
            for (int i = 0; i < 4; i++) {
                int x = current[0];
                int y = current[1];
                // Continue in direction until hitting a wall
                while (x >= 0 && x < rows && y >= 0 && y < cols && maze[x][y] == 0) {
                    x += deltaX[i];
                    y += deltaY[i];
                }
                // Backtrack last move
                x -= deltaX[i];
                y -= deltaY[i];
                if (!visited[x][y]) {
                    bfsQueue.offer(new int[]{x, y});
                    visited[x][y] = true;
                }
            }
        }
        return false;
    }
}

The "The Maze" problem is efficiently addressed using the Java programming language in the provided solution. Here's a breakdown on how the code operates and accomplishes the task of finding a path in the maze:

  • Maze Representation and Input: The maze is represented as a 2D array where 0 signifies a passable cell and 1 an impassable wall. Inputs to the function include the maze itself and start/end coordinates as arrays.

  • Data Structures Used:

    • Visited Array: A 2D boolean array that keeps track of visited cells.
    • BFS Queue: A Queue holding array coordinates facilitating a breadth-first search.
  • Algorithm Initialization:

    • The start cell is marked as visited and then added to the BFS queue.
  • Breadth-First Search (BFS) Implementation:

    1. Begin a loop over the BFS queue until it's empty, processing each cell.
    2. Check each dequeued cell. If it matches the end location, return true indicating a path exists.
    3. Explore possible movements from the current cell in four directions (up, right, down, left) using arrays deltaX and deltaY.
    4. Upon encountering walls or boundaries, backtrack to the last valid cell.
    5. If this new cell hasn’t been visited, mark it as visited and enqueue it.
  • End of Algorithm: If no path is found by the time the queue empties, return false.

This code uses BFS for exploration, which ensures that the shortest path in an unweighted maze is found due to the layer-by-layer nature of BFS. Furthermore, the solution is robust in adhering to boundaries and avoiding revisits, making it efficient and effective for solving large mazes. The use of a queue in conjunction with the visited matrix optimally fosters both memory and performance efficiency.

  • Python
python
class Solution:
    def pathExists(self, grid: List[List[int]], source: List[int], target: List[int]) -> bool:
        rows = len(grid)
        cols = len(grid[0])
        visited = [[False] * cols for _ in range(rows)]
        q = deque()
            
        q.append(source)
        visited[source[0]][source[1]] = True
        directionsX = [0, 1, 0, -1]
        directionsY = [-1, 0, 1, 0]
    
        while q:
            current = q.popleft()
            if current[0] == target[0] and current[1] == target[1]:
                return True
    
            for j in range(4):
                x = current[0]
                y = current[1]
                # Continue moving in the direction until hitting a wall or boundary
                while x >= 0 and x < rows and y >= 0 and y < cols and grid[x][y] == 0:
                    x += directionsX[j]
                    y += directionsY[j]
                # Move back to the last valid position
                x -= directionsX[j]
                y -= directionsY[j]
                if not visited[x][y]:
                    q.append([x, y])
                    visited[x][y] = True
        return False

The provided Python solution implements a method to determine if a path exists between a source and target point within a maze represented as a grid. The grid is a 2D list where open paths are denoted by 0 and walls by 1. The solution leverages Breadth-First Search (BFS) to explore the maze.

  • Initialize data structures for tracking rows and columns size, visited cells, and BFS queue starting from the source point.
  • Continuously explore the maze by dequeuing elements from the queue and checking all possible directions.
  • For each direction, move continuously until hitting a wall or boundary, then adjust to the last possible open cell.
  • If this cell hasn't been visited, enqueue it for further exploration.
  • Return True if the target is reached during the BFS process; otherwise, return False after all possibilities have been exhausted.

The approach ensures that every reachable area within the maze is explored using only valid moves, accounting for maze boundaries and internal walls, and guarantees an efficient search to maintain performance.

Comments

No comments yet.