bucktrakc10

def read_maze(filename):
    """Чтение лабиринта из файла"""
    with open(filename, 'r') as f:
        return [line.strip().split() for line in f]

def count_paths(maze, mouse_x, mouse_y, cheese_x, cheese_y):
    """
    Рекурсивный поиск путей к сыру

    Параметры:
    - maze: лабиринт
    - mouse_x, mouse_y: текущие координаты мышки
    - cheese_x, cheese_y: координаты сыра
    """
    N = len(maze)

    # Создаем матрицу посещенных клеток
    visited = [[False for _ in range(N)] for _ in range(N)]

    def is_valid_move(x, y):
        """Проверка корректности хода"""
        return (
            0 <= x < N and
            0 <= y < N and
            maze[x][y] == ' ' and  # Проверка на пустую клетку
            not visited[x][y]      # Клетка не посещена
        )

    def find_paths_recursive(current_x, current_y):
        """
        Рекурсивный поиск путей

        Базовые случаи:
        1. Мышка достигла сыра
        2. Невозможность движения
        """
        # Достижение цели
        if current_x == cheese_x and current_y == cheese_y:
            return 1

        # Отмечаем текущую клетку как посещенную
        visited[current_x][current_y] = True

        # Возможные направления движения (вверх, вправо, вниз, влево)
        directions = [
            (-1, 0),  # Вверх
            (0, 1),   # Вправо
            (1, 0),   # Вниз
            (0, -1)   # Влево
        ]

        total_paths = 0

        # Исследование каждого направления
        for dx, dy in directions:
            next_x, next_y = current_x + dx, current_y + dy

            # Проверка возможности перемещения
            if is_valid_move(next_x, next_y):
                # Рекурсивный вызов для следующей позиции
                total_paths += find_paths_recursive(next_x, next_y)

        # Возвращаем клетку в непосещенное состояние (backtracking)
        visited[current_x][current_y] = False

        return total_paths

    # Начинаем поиск путей с начальной позиции мышки
    return find_paths_recursive(mouse_x, mouse_y)

def main():
    # Чтение лабиринта
    maze = read_maze('maze.txt')

    # Координаты мышки и сыра (указать правильные)
    mouse_x, mouse_y = 1, 1  # Начальная позиция мышки
    cheese_x, cheese_y = 3, 3  # Позиция сыра

    # Подсчет путей
    paths = count_paths(maze, mouse_x, mouse_y, cheese_x, cheese_y)
    print(f"Количество путей: {paths}")

if __name__ == "__main__":
    main()