bucktrack10

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

def solve_maze(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(x, y):
        """Рекурсивный поиск путей"""
        # Достижение сыра
        if x == cheese_x and y == cheese_y:
            return 1

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

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

        for dx, dy in moves:
            next_x, next_y = x + dx, y + dy

            if is_valid_move(next_x, next_y):
                paths += find_paths(next_x, next_y)

        # Возвращаем клетку в непосещенное состояние
        visited[x][y] = False

        return paths

    return find_paths(mouse_x, mouse_y)

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

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

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

if __name__ == "__main__":
    main()