Problem Description

The Maze problem presents you with a 2D grid representing a maze, where each cell can either be empty (0) or a wall (1). You are given a start position and a destination position within the maze. Your goal is to determine if there is a path for a ball to travel from the start position to the destination position, following these rules:

• The ball can move up, down, left, or right, but it rolls in a chosen direction until it hits a wall or the maze boundary.
• Once the ball stops (because it hits a wall or boundary), you can choose the next direction to roll.
• The ball cannot stop in the middle of an empty space except at the start or after hitting a wall.
• It is not allowed to pass through walls or stop in them.
• Return true if the ball can reach the destination (stop exactly at the destination cell), otherwise return false.

Key constraints:

• There may be multiple possible paths, but you only need to determine if at least one valid path exists.
• Cells may not be revisited unnecessarily (to avoid cycles and infinite loops).

Thought Process

At first glance, this problem seems similar to classic pathfinding in a grid, like finding a path in a maze using BFS (Breadth-First Search) or DFS (Depth-First Search). However, the twist is that the ball keeps rolling in a direction until it hits a wall or boundary, so you cannot simply move one cell at a time.

A brute-force approach might try all possible paths, but this is inefficient and could revisit the same position multiple times. Instead, we need to adapt BFS or DFS to account for the "rolling" behavior: each move continues until a wall or edge is hit, and only then can we choose a new direction.

To optimize, we should:

• Track visited positions to avoid redundant work and cycles.
• Simulate rolling in each direction fully before choosing the next move.
• Use a queue (for BFS) or recursion/stack (for DFS) to manage the search process.

Solution Approach

Let's break down the steps to solve the Maze problem:

1. Initialize:
   • Create a queue (for BFS) or use recursion (for DFS) to store positions where the ball stops.
   • Maintain a visited matrix or set to track cells we've already stopped at.
2. Start the Search:
   • Add the start position to the queue and mark it as visited.
3. Process Each Position:
   • While the queue is not empty, remove the front position.
   • If this position is the destination, return true.
   • For each of the four directions (up, down, left, right):
   • Roll the ball in that direction until it hits a wall or boundary.
   • Record the stopping cell just before the wall/boundary.
   • If this cell hasn't been visited, mark it visited and add it to the queue.
4. Termination:
   • If the queue is empty and the destination hasn't been reached, return false.

Design Choices:

• We use BFS because it naturally finds the shortest path (if required). DFS is also acceptable since we only care about existence, not length.
• The visited set ensures we don't revisit cells, preventing infinite loops.
• Simulating the roll in each direction in a loop helps us efficiently find all possible stopping points.

Example Walkthrough

Let's consider a sample maze:

  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]
  

Step-by-step:

• Start at (0,4). Mark as visited.
• Try rolling left: stops at (0,3). Mark as visited and enqueue.
• Try rolling down: stops at (4,4). This is the destination! Return true.
• Other directions either hit walls or boundaries immediately.

The algorithm finds a direct path by rolling down from the start, demonstrating how the rolling logic works.

Time and Space Complexity

Brute-force approach:

• Time complexity: Potentially exponential, since it may revisit the same cell in different ways, leading to an explosion of paths.
• Space complexity: Also exponential in the worst case, due to call stack or queue size.

• Time complexity: O(m * n), where m is the number of rows and n is the number of columns. Each cell is visited at most once as a stopping point.
• Space complexity: O(m * n) for the visited set and the queue.

The rolling in each direction is at most O(m) or O(n) per move, but since each cell is only a stopping point once, the overall complexity is linear in the number of cells.

Summary

The Maze problem is a variation of classic pathfinding, made unique by the ball's rolling behavior. The key insight is to simulate the ball's full roll in each direction and only consider new stopping points. By tracking visited positions and using BFS or DFS, we efficiently determine if a path exists. The approach is elegant because it leverages standard search techniques with a simple adaptation for the rolling mechanic, ensuring both correctness and efficiency.

Code Implementation

from collections import deque

class Solution:
    def hasPath(self, maze, start, destination):
        m, n = len(maze), len(maze[0])
        visited = [[False] * n for _ in range(m)]
        queue = deque()
        queue.append((start[0], start[1]))
        visited[start[0]][start[1]] = True

        directions = [(-1,0), (1,0), (0,-1), (0,1)]
        while queue:
            x, y = queue.popleft()
            if [x, y] == destination:
                return True
            for dx, dy in directions:
                nx, ny = x, y
                # Roll the ball until it hits a wall or boundary
                while 0 <= nx + dx < m and 0 <= ny + dy < n and maze[nx + dx][ny + dy] == 0:
                    nx += dx
                    ny += dy
                if not visited[nx][ny]:
                    visited[nx][ny] = True
                    queue.append((nx, ny))
        return False
      

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

class Solution {
public:
    bool hasPath(vector<vector<int>>& maze, vector<int>& start, vector<int>& destination) {
        int m = maze.size(), n = maze[0].size();
        vector<vector<bool>> visited(m, vector<bool>(n, false));
        queue<pair<int, int>> q;
        q.push({start[0], start[1]});
        visited[start[0]][start[1]] = true;

        int dirs[4][2] = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        while (!q.empty()) {
            auto [x, y] = q.front(); q.pop();
            if (x == destination[0] && y == destination[1]) return true;
            for (auto& dir : dirs) {
                int nx = x, ny = y;
                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];
                }
                if (!visited[nx][ny]) {
                    visited[nx][ny] = true;
                    q.push({nx, ny});
                }
            }
        }
        return false;
    }
};
      

import java.util.*;

class Solution {
    public boolean hasPath(int[][] maze, int[] start, int[] destination) {
        int m = maze.length, n = maze[0].length;
        boolean[][] visited = new boolean[m][n];
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{start[0], start[1]});
        visited[start[0]][start[1]] = true;

        int[][] dirs = {{-1,0}, {1,0}, {0,-1}, {0,1}};
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            if (pos[0] == destination[0] && pos[1] == destination[1]) return true;
            for (int[] dir : dirs) {
                int nx = pos[0], ny = pos[1];
                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];
                }
                if (!visited[nx][ny]) {
                    visited[nx][ny] = true;
                    queue.offer(new int[]{nx, ny});
                }
            }
        }
        return false;
    }
}
      

/**
 * @param {number[][]} maze
 * @param {number[]} start
 * @param {number[]} destination
 * @return {boolean}
 */
var hasPath = function(maze, start, destination) {
    const m = maze.length, n = maze[0].length;
    const visited = Array.from({length: m}, () => Array(n).fill(false));
    const queue = [[start[0], start[1]]];
    visited[start[0]][start[1]] = true;
    const dirs = [[-1,0],[1,0],[0,-1],[0,1]];
    while (queue.length > 0) {
        const [x, y] = queue.shift();
        if (x === destination[0] && y === destination[1]) return true;
        for (const [dx, dy] of dirs) {
            let nx = x, ny = y;
            while (
                nx + dx >= 0 && nx + dx < m &&
                ny + dy >= 0 && ny + dy < n &&
                maze[nx + dx][ny + dy] === 0
            ) {
                nx += dx;
                ny += dy;
            }
            if (!visited[nx][ny]) {
                visited[nx][ny] = true;
                queue.push([nx, ny]);
            }
        }
    }
    return false;
};