1. Depth First Search

Intuition

Unlike typical grid problems where movement is one cell at a time, the ball in this maze rolls continuously in one direction until it hits a wall. This means the ball can only stop at specific positions: cells adjacent to walls.

We can model this as a graph where each stopping position is a node, and edges connect positions reachable by rolling in any of the four directions. DFS explores all reachable stopping positions to determine if the destination is among them.

Algorithm

1. Create a visited matrix to track stopping positions already explored.
2. Define a recursive dfs function:
   • If the current position was already visited, return false.
   • If the current position equals the destination, return true.
   • Mark the current position as visited.
   • For each of the four directions (up, down, left, right):
     • Roll the ball continuously until it hits a wall or boundary.
     • Step back one position to find where the ball actually stops.
     • Recursively call dfs from this stopping position.
   • Return true if any direction leads to the destination.
3. Start dfs from the initial position and return the result.

class Solution:
    def dfs(self, m, n, maze, curr, destination, visit):
        if visit[curr[0]][curr[1]]:
            return False
        if curr[0] == destination[0] and curr[1] == destination[1]:
            return True

        visit[curr[0]][curr[1]] = True
        dirX = [0, 1, 0, -1]
        dirY = [-1, 0, 1, 0]

        for i in range(4):
            r = curr[0]
            c = curr[1]
            # Move the ball in the chosen direction until it can.
            while r >= 0 and r < m and c >= 0 and c < n and maze[r][c] == 0:
                r += dirX[i]
                c += dirY[i]
            # Revert the last move to get the cell to which the ball rolls.
            if self.dfs(m, n, maze, [r - dirX[i], c - dirY[i]], destination, visit):
                return True
        return False

    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        m = len(maze)
        n = len(maze[0])
        visit = [[False] * n for _ in range(m)]
        return self.dfs(m, n, maze, start, destination, visit)

Time & Space Complexity

• Time complexity: $O(m \cdot n \cdot (m + n))$
• Space complexity: $O(m \cdot n)$

Where $m$ and $n$ are the number of rows and columns in maze.

---

2. Breadth First Search

Intuition

BFS offers an alternative traversal strategy that explores all stopping positions at each "distance level" before moving deeper. While DFS might go deep into one path before backtracking, BFS systematically explores positions in order of how many rolls it takes to reach them.

The core rolling mechanic remains the same: the ball rolls until hitting a wall, and we only consider positions where the ball actually stops.

Algorithm

1. Initialize a visited matrix and a queue with the starting position.
2. Mark the starting position as visited.
3. While the queue is not empty:
   • Dequeue the current position.
   • If it equals the destination, return true.
   • For each of the four directions:
     • Roll the ball until it hits a wall or boundary.
     • Step back to find the stopping position.
     • If not visited, mark it visited and add to the queue.
4. If the queue empties without finding the destination, return false.

class Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        m = len(maze)
        n = len(maze[0])
        visit = [[False] * n for _ in range(m)]
        queue = deque()
        
        queue.append(start)
        visit[start[0]][start[1]] = True
        dirX = [0, 1, 0, -1]
        dirY = [-1, 0, 1, 0]

        while queue:
            curr = queue.popleft()
            if curr[0] == destination[0] and curr[1] == destination[1]:
                return True

            for i in range(4):
                r = curr[0]
                c = curr[1]
                # Move the ball in the chosen direction until it can.
                while r >= 0 and r < m and c >= 0 and c < n and maze[r][c] == 0:
                    r += dirX[i]
                    c += dirY[i]
                # Revert the last move to get the cell to which the ball rolls.
                r -= dirX[i]
                c -= dirY[i]
                if not visit[r][c]:
                    queue.append([r, c])
                    visit[r][c] = True
        return False

Time & Space Complexity

• Time complexity: $O(m \cdot n \cdot (m + n))$
• Space complexity: $O(m \cdot n)$

Where $m$ and $n$ are the number of rows and columns in maze.