https://leetcode.com/problems/nearest-exit-from-entrance-in-maze/

leetcode1926.py

from queue import SimpleQueue
from dataclasses import dataclass, field
from pprint import pprint

@dataclass(frozen=True, eq=True)
class Point:
    x: int
    y: int

@dataclass
class SearchNode:
    pos: Point
    path: list[Point] = field(default_factory=list)

class Solution:
    def nearestExit(self, maze: List[List[str]], entrance: List[int]) -> int:
        visited = set()
        x, y = entrance[0], entrance[1]
        entrance_pos = Point(x, y)

        nodes_to_visit = SimpleQueue()
        nodes_to_visit.put(SearchNode(Point(x, y), []))

        while not nodes_to_visit.empty():
            current = nodes_to_visit.get()
            visited.add(current.pos)
            # pprint(current)
            # if we hit the border of the maze
            if current.pos.x == 0 or current.pos.y == 0 or current.pos.x == len(maze) - 1 or current.pos.y == len(maze[0]) - 1:
                if current.pos != entrance_pos:
                    return len(current.path)
            
            candidate_points = [
                Point(current.pos.x - 1, current.pos.y),
                Point(current.pos.x + 1, current.pos.y),
                Point(current.pos.x, current.pos.y - 1),
                Point(current.pos.x, current.pos.y + 1),
            ]

            for candidate in candidate_points:
                if can_travel(candidate, visited, maze):
                    nodes_to_visit.put(SearchNode(candidate, current.path + [candidate]))
        
        # if we didn't return, we never found an exit
        return -1

def can_travel(point: Point, visited: set[Point], maze: list[list[str]]) -> bool:
    if point in visited:
        return False
    if point.x < 0 or point.x >= len(maze):
        return False
    if point.y < 0 or point.y >= len(maze[0]):
        return False
    if maze[point.x][point.y] == '+':
        return False

    return True