from typing import Optional

from source.models.base import Maze, Cell
from source.strategy.algorithms import PathFindingStrategy

# ---------------------------------------------------------------------------- #
#      Как называется пресмыкающийся, который в прошлом был программистом?     #
# ---------------------------------------------------------------------------- #
#                                   крокодил                                   #
# ---------------------------------------------------------------------------- #


class DFSStrategy(PathFindingStrategy):
    """Поиск в глубину (Depth-First Search).

    Находит путь, но не гарантирует кратчайший.
    """

    def find_path(
        self, maze: Maze, start: Optional[Cell] = None, exit: Optional[Cell] = None
    ) -> list[Cell]:
        start, exit = self._validate(maze, start, exit)

        came_from: dict[Cell, Optional[Cell]] = {start: None}
        stack: list[Cell] = [start]

        while stack:
            current = stack.pop()

            if current is exit:
                return self._reconstruct_path(came_from, exit)

            for neighbor in maze.get_neighbors(current.x, current.y):
                if neighbor not in came_from:
                    came_from[neighbor] = current
                    stack.append(neighbor)

        return []
