backtrack10

import os

def find_cheese_paths(maze, start_x, start_y, cheese_x, cheese_y):
    """
    Рекурсивная функция для подсчета путей мышки к сыру в лабиринте

    Параметры:
    maze - двумерный список лабиринта
    start_x, start_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] != 'M' and
            not visited[x][y]
        )

    def dfs(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 += dfs(next_x, next_y)

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

        return total_paths

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

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

def main():
    # Путь к файлу с лабиринтом
    maze_file = 'maze.txt'

    # Чтение лабиринта
    maze = read_maze_from_file(maze_file)

    # Параметры: начальная позиция мышки и позиция сыра
    start_x, start_y = 0, 0     # Пример начальной позиции
    cheese_x, cheese_y = 4, 4   # Пример позиции сыра

    # Подсчет путей
    paths_count = find_cheese_paths(maze, start_x, start_y, cheese_x, cheese_y)

    print(f"Количество различных путей: {paths_count}")

if __name__ == "__main__":
    main()