490. The Maze

Link

Kinda greedy approach

bfs

class Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:

        m = len(maze)
        n = len(maze[0])
        dq = deque([start])

        s = set()

        while dq:
            lens = len(dq)

            for _ in range(lens):
                x, y = dq.popleft()

                if [x, y] == destination:
                    return True

                if (x,y) in s:
                    continue

                s.add((x,y))

                for i , j in [(0,1), (0,-1), (1,0), (-1, 0)]:
                    k = 1

                    while 0 <= x + i * k < m and 0 <= y + j * k < n:
                        if maze[x + i * k][y + j * k] == 1:
                            break
                        k += 1
                    
                    k -= 1
                    dq.append([x + i * k, y + j * k])

        return False

dfs

class Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:

        m = len(maze)
        n = len(maze[0])

        self.res = False

        s = set()

        def dfs(i, j):
            if self.res:
                return

            if i == destination[0] and j == destination[1]:
                self.res = True
                return

            if (i, j) in s:
                return

            s.add((i, j))

            for x, y in [(0,1), (0,-1),(1,0),(-1,0)]:
                dx, dy = x, y
                
                while (0 <= i + dx < m and 0 <= j + dy < n) and maze[i+dx][j+dy] == 0:
                    dx += x
                    dy += y

                dfs(i+dx-x, j+dy-y)

        dfs(start[0], start[1])

        return self.res