490. The Maze.md

490. The Maze (Hard)

Algorithm 1 Brute Force BFS

1. use a queue to store all possible path in the current round.
2. use a visted node
3. use an array for 4 directions
4. each iter,
   • pop from queueand
   • check if meet target return if true
   • go all 4 directions use a while loop until hitting the wall
   • if not visited, add to queue and mark it as visted.
5. return false since target not meet.

import numpy as np
class Solution:
    def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
        visited = np.zeros((len(maze), len(maze[0])))
        direction = [[1,0], [0, 1], [-1, 0], [0, -1]]
        mazeQ = deque()
        mazeQ.append(start)
        visited[start[0]][start[1]] = True
        
        while(mazeQ):
            oneNode = mazeQ.popleft()
            print(oneNode)
            if oneNode == destination:
                return True
            for oneDir in direction:
                x = oneNode[0] + oneDir[0]
                y = oneNode[1] + oneDir[1]
                while(x >= 0 and y >= 0 and x < len(maze) and y < len(maze[0]) and maze[x][y] == 0):
                    x += oneDir[0]
                    y += oneDir[1]
                x -= oneDir[0]
                y -= oneDir[1]
                if not visited[x][y]:
                    mazeQ.append([x, y])
                    visited[x][y] = True
        return False