Solution Explanation for LeetCode 490: The Maze

This problem asks whether a ball can reach a destination in a maze, given its starting position. The ball rolls until it hits a wall. We can solve this using either Depth-First Search (DFS) or Breadth-First Search (BFS).

Approach 1: Depth-First Search (DFS)

This approach recursively explores all possible paths from the starting point.

Algorithm:

1. dfs(i, j) function: This recursive function takes the current row (i) and column (j) as input.
2. Base Cases:
   • If vis[i][j] is true (already visited), return.
   • If [i, j] is the destination, return.
3. Mark as Visited: Set vis[i][j] = True.
4. Explore Directions: Iterate through all four directions (up, down, left, right). For each direction:
   • Simulate the ball rolling in that direction until it hits a wall.
   • Recursively call dfs on the coordinates where the ball stops.

Code (Python):

def hasPath(maze, start, destination):
    m, n = len(maze), len(maze[0])
    vis = [[False] * n for _ in range(m)]
 
    def dfs(i, j):
        if vis[i][j]:
            return False
        vis[i][j] = True
        if [i, j] == destination:
            return True
        for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
            x, y = i, j
            while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0:
                x, y = x + a, y + b
            if dfs(x, y):
                return True
        return False
 
    return dfs(start[0], start[1])
 

Time Complexity: O(MN), where M and N are the dimensions of the maze. In the worst case, we might visit every cell. Space Complexity: O(MN) due to the visited array vis in the worst case. The recursive call stack could also reach O(M*N) in a worst-case scenario of a very long path.

Approach 2: Breadth-First Search (BFS)

This approach uses a queue to explore the maze level by level.

Algorithm:

1. Initialization: Create a queue q and a set vis to track visited cells. Add the start to q and vis.
2. Iteration: While the queue is not empty:
   • Dequeue the current cell (i, j).
   • For each direction:
     • Simulate the ball rolling until it hits a wall.
     • If the ball reaches the destination, return True.
     • If the stopping cell is not in vis, add it to q and vis.
3. No Path: If the queue becomes empty without finding the destination, return False.

Code (Python):

from collections import deque
 
def hasPath(maze, start, destination):
    m, n = len(maze), len(maze[0])
    q = deque([start])
    vis = {tuple(start)}  # Use tuple for hashability
 
    while q:
        i, j = q.popleft()
        if [i, j] == destination:
            return True
        for a, b in [[0, -1], [0, 1], [1, 0], [-1, 0]]:
            x, y = i, j
            while 0 <= x + a < m and 0 <= y + b < n and maze[x + a][y + b] == 0:
                x, y = x + a, y + b
            if (x, y) not in vis:
                vis.add((x, y))
                q.append([x, y])
    return False

Time Complexity: O(MN). Similar to DFS, we might visit every cell in the worst case. Space Complexity: O(MN) in the worst case, to store visited cells in vis and the queue q.

Both approaches have the same time and space complexity. BFS generally performs better in practice for finding the shortest path, although that's not directly relevant to this problem which only needs to determine if a path exists. DFS might be slightly more concise in some implementations. The choice between them often depends on personal preference or specific constraints of the problem. The provided solutions include implementations in Python, Java, C++, and Go for both DFS and BFS approaches.