*490. The Maze

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

solution

class Solution(object):
    def hasPath(self, maze, start, destination):
        n_row = len(maze)
        n_col = len(maze[0])
        queue = collections.deque([start])
        visited = set()
        visited.add(tuple(start))

        while queue:
            row, col = queue.popleft()
            for dx, dy in [[0, -1], [0, 1], [-1, 0], [1, 0]]:
                new_row, new_col = row, col
                # "撞到墙才改变方向", 前面对方向循环，这里判断时加一个条件: 这个方向的maze一直为0, 一直同一个方向往下
                while 0 <= new_row + dx < n_row and 0 <= new_col + dy < n_col and maze[new_row + dx][new_col + dy] == 0:
                    new_row += dx
                    new_col += dy

                if [new_row, new_col] == destination:
                    return True

                if (new_row, new_col) not in visited:
                    visited.add((new_row, new_col))
                    queue.append((new_row, new_col))
        return False

时间复杂度：O() 空间复杂度：O()

follow up

*505. The Maze II

class Solution:
    def shortestDistance(self, maze: List[List[int]], start: List[int], destination: List[int]) -> int:
        rows, cols = len(maze), len(maze[0])
        directions = (-1, 0, 1, 0, -1)

        start_i, start_j = start
        dest_i, dest_j = destination

        queue = collections.deque([(start_i, start_j)])

        distance = [[math.inf] * cols for _ in range(rows)]
        distance[start_i][start_j] = 0  # Starting point distance is 0

        while queue:
            i, j = queue.popleft()

            # Using pairwise to iterate through the directions
            for a, b in itertools.pairwise(directions):
                x, y, current_dist = i, j, distance[i][j]

                # Move in the current direction until hitting a wall
                while 0 <= x + a < rows and 0 <= y + b < cols and maze[x + a][y + b] == 0:
                    x += a
                    y += b
                    current_dist += 1

                # If minimum distance can be updated
                if current_dist < distance[x][y]:
                    distance[x][y] = current_dist
                    # Add new position to the queue for further exploration
                    queue.append((x, y))

        return -1 if distance[dest_i][dest_j] == inf else distance[dest_i][dest_j]

时间复杂度：O() 空间复杂度：O()

*499. The Maze III

时间复杂度：O() 空间复杂度：O()