Maze

Intuition

Even though the ball moves cell by cell, the only positions that matter for decisions are the places where it can actually stop, which are next to walls. We therefore build a graph whose nodes are stopping positions and run breadth-first search over them. From a given stop, rolling in one of the four directions until a wall blocks the way produces exactly one neighboring stop. We mark stops as visited so the search does not loop, and we succeed the moment the destination appears as a stop. If the queue empties without landing on the destination, the ball can never rest there.

Algorithm walkthrough

1. 1Create a visited matrix, enqueue the start position, and mark it visited.
2. 2Pop a stopping position; if it equals the destination, return true.
3. 3For each of the four directions, roll from the current stop, advancing while the next cell is in-bounds and open.
4. 4The cell where the roll halts is a neighboring stop; if it has not been visited, mark it and enqueue it.
5. 5Continue until the queue empties; if the destination was never dequeued, return false.

Implementation

from collections import deque

class Solution:
    def hasPath(self, maze: list[list[int]], start: list[int], destination: list[int]) -> bool:
        m, n = len(maze), len(maze[0])
        directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        visited = [[False] * n for _ in range(m)]
        queue = deque([(start[0], start[1])])
        visited[start[0]][start[1]] = True
        while queue:
            row, col = queue.popleft()
            if row == destination[0] and col == destination[1]:
                return True
            for dr, dc in directions:
                nr, nc = row, col
                while 0 <= nr + dr < m and 0 <= nc + dc < n and maze[nr + dr][nc + dc] == 0:
                    nr += dr
                    nc += dc
                if not visited[nr][nc]:
                    visited[nr][nc] = True
                    queue.append((nr, nc))
        return False