Problem statement

https://leetcode.com/problems/the-maze/

Solution

We can use usual dfs or bfs traversal, but it will have O(V * max(m, n)) time complexity, where V is number of empty cells and m, n are dimensions of our maze.

We can use dp to precalculate all possible moves of ball given each place: the position where it will stop when it goes down, up, left or right. Then, when we do dfs or bfs traversal we can do steps in O(1) time.

Complexity

Overall time complexity is O(mn), space is also O(mn) to keep dp table and to keep visited noted.

Code

class Solution:
    def hasPath(self, maze, start, D):
        @lru_cache(None)
        def dp(x, y, dx, dy):
            if not 0 <= x+dx < m or not 0 <= y+dy < n: return (x, y)
            if maze[x+dx][y+dy] == 1: return (x, y)
            return dp(x+dx, y+dy, dx, dy)

        def dfs(x, y):
            visited.add((x, y))
            for dx, dy in dirs:
                x2, y2 = dp(x, y, dx, dy)
                if (x2, y2) in visited: continue
                dfs(x2, y2)

        visited = set()
        m, n = len(maze), len(maze[0])
        dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]]
        dfs(start[0], start[1])
        return (D[0], D[1]) in visited