import sys

from strategy import PathFindingStrategy
from Maze import Maze, Cell

sys.setrecursionlimit(15000)


class DFSStrategy(PathFindingStrategy):
    def findPath(self, maze: Maze, start, exit):

        if not start or not exit:
            return [], 0

        visited = set()
        path = []

        count_cell = 0

        def dfs(root: Cell) -> bool:
            visited.add(root)
            path.append(root)
            # count_cell += 1

            if root == exit:
                return True

            neighbors = maze.getNeighbors(root)
            for neighbor in neighbors:
                if neighbor not in visited:
                    if dfs(neighbor):
                        return True

            path.pop()
            return False

        if dfs(start):
            return path, len(visited)

        return [], len(visited)
