490. The Maze - cocoder39/coco39_LC GitHub Wiki

Option 1: DFS + tracking each position + direction

Each state is represented by (row, col, direction)
- visited can be compressed to 2-dimension array visited[row][col] and use bit to track each direction eg 0101 means ball has passed through direction 0 and 2.
T = O(M * N)

class Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        for d in range(4):
            if self.helper(maze, set(), start[0], start[1], d, destination):
                return True
        return False
    
    def helper(self, maze, visited, curRow, curCol, curDir, destination):
        DIR = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        m, n = len(maze), len(maze[0])
        
        visited.add((curRow, curCol, curDir))
        
        # next grid is not wall
        dx, dy = DIR[curDir]
        newRow, newCol = curRow + dx, curCol + dy
        if 0 <= newRow < m and 0 <= newCol < n and maze[newRow][newCol] != 1:
            if (newRow, newCol, curDir) in visited:
                return False
            
            return self.helper(maze, visited, newRow, newCol, curDir, destination)
        
        # next grid is wall
        if curRow == destination[0] and curCol == destination[1]:
            return True
        
        for d in range(4):
            if (curRow, curCol, d) not in visited:
                if self.helper(maze, visited, curRow, curCol, d, destination):
                    return True
        return False

Option 2: DFS + tracking stop position (no tracking for direction since every direction has been explored)

Option 3: BFS