bDYn7e - Online Python3 Interpreter & Debugging Tool

# fields_and_stones_longest.py
import random
import time
import sys

# Налаштування рекурсії
sys.setrecursionlimit(10000)

# ------------------------
# Генерація поля
# 0 = поле ('.'), 1 = камінь ('#')
# ------------------------
def generate_field(N, M, p):
    grid = [[1 if random.random() < p else 0 for _ in range(M)] for _ in range(N)]
    grid[N-1][0] = 0   # старт (лівий нижній)
    grid[0][M-1] = 0   # фініш (правий верхній)
    return grid

# ------------------------
# Коротка перевірка існування шляху (BFS) перед тривалим DFS
# щоб не запускати довгий пошук коли шлях зовсім відсутній
# ------------------------
from collections import deque
def exists_path_bfs(grid):
    N, M = len(grid), len(grid[0])
    start = (N-1,0)
    goal = (0, M-1)
    if grid[start[0]][start[1]] != 0 or grid[goal[0]][goal[1]] != 0:
        return False
    q = deque([start])
    vis = [[False]*M for _ in range(N)]
    vis[start[0]][start[1]] = True
    dirs = [(1,0),(-1,0),(0,1),(0,-1)]
    while q:
        r,c = q.popleft()
        if (r,c) == goal:
            return True
        for dr,dc in dirs:
            nr, nc = r+dr, c+dc
            if 0 <= nr < N and 0 <= nc < M and not vis[nr][nc] and grid[nr][nc] == 0:
                vis[nr][nc] = True
                q.append((nr,nc))
    return False

# ------------------------
# Пошук найдовшого простого шляху (DFS з відкатом + таймаут)
# Параметри:
#   time_limit - сек., скільки максимум шукати
#   randomize - чи випадково перемішувати порядок сусідів для різноманіття
# Повертає: найкращий шлях як список клітин від старту до фінішу (включно) або None
# ------------------------
def longest_path_dfs(grid, time_limit=1.5, randomize=True):
    N, M = len(grid), len(grid[0])
    start = (N-1, 0)
    goal = (0, M-1)
    dirs = [(1,0), (0,1), (-1,0), (0,-1)]  # порядок можна міняти
    best_path = None
    best_len = -1
    start_time = time.time()
    max_nodes = 10**6
    nodes = 0

    # Пріоритет: спробуємо шукати більш глибоко — порядок сусідів можна перемішати
    import random as _rnd

    visited = [[False]*M for _ in range(N)]
    path = []

    def dfs(r,c):
        nonlocal best_len, best_path, nodes
        # таймаут/лиміт на відвідані вузли
        if time.time() - start_time > time_limit:
            return
        nodes += 1
        if nodes > max_nodes:
            return

        # якщо дійшли до goal — оновити кращий шлях
        if (r,c) == goal:
            if len(path) > best_len:
                best_len = len(path)
                best_path = path.copy()
            # не повертаємось далі з goal (нам потрібно goal бути останнім)
            return

        # Порядок сусідів: спочатку ті, що ведуть ближче до goal (гіпо), потім інші
        neighs = []
        for dr,dc in dirs:
            nr, nc = r+dr, c+dc
            if 0 <= nr < N and 0 <= nc < M and not visited[nr][nc] and grid[nr][nc] == 0:
                # не заходити в goal, якщо goal вже в path (не буде)
                # обчислимо евклідну відстань або манхеттен
                dist = abs(nr - goal[0]) + abs(nc - goal[1])
                neighs.append((dist, nr, nc))
        # сортуємо за зменшенням відстані -> спочатку ті, що далі від цілі, щоб робити довші «змійки»
        neighs.sort(reverse=True, key=lambda x: x[0])
        if randomize:
            # невелика випадкова перестановка серед тих з однаковою дистанцією
            i = 0
            while i < len(neighs):
                j = i
                while j < len(neighs) and neighs[j][0] == neighs[i][0]:
                    j += 1
                # shuffle block [i, j)
                block = neighs[i:j]
                _rnd.shuffle(block)
                neighs[i:j] = block
                i = j

        for _, nr, nc in neighs:
            # якщо досягли ліміту часу, виходимо
            if time.time() - start_time > time_limit:
                return
            # відвідуємо
            visited[nr][nc] = True
            path.append((nr,nc))
            dfs(nr,nc)
            # відкат
            path.pop()
            visited[nr][nc] = False
            # optional pruning: якщо знайшли шлях максимальної можливої довжини (всі поля), можна зупинитися
            # але ми не рахуємо тут максимально можливу глобальну довжину, тому пропускаємо

    # початковий захід: старт має бути першою позицією у path
    if grid[start[0]][start[1]] != 0 or grid[goal[0]][goal[1]] != 0:
        return None

    visited[start[0]][start[1]] = True
    path.append(start)
    dfs(start[0], start[1])
    # якщо нічого не знайдено (можливо шлях існував тільки прямий) — best_path може бути None
    visited[start[0]][start[1]] = False
    path.pop()

    return best_path

# ------------------------
# Вивід карти: пронумерований шлях (0 = старт), '.' для незораного, '#' для каменю
# Клітинка має ширину під найбільший індекс
# ------------------------
def print_board_numbered(grid, path):
    N, M = len(grid), len(grid[0])
    step = {}
    if path:
        for i, cell in enumerate(path):
            step[cell] = i

    max_step = max(step.values()) if step else 0
    width = max(3, len(str(max_step)) + 2)

    def cell_str(s):
        return str(s).center(width)

    print()
    for r in range(N):
        row_cells = []
        for c in range(M):
            if (r,c) in step:
                row_cells.append(cell_str(step[(r,c)]))
            elif grid[r][c] == 1:
                row_cells.append(cell_str("#"))
            else:
                row_cells.append(cell_str("."))
        print("".join(row_cells))
    print()

# ------------------------
# MAIN (українською)
# ------------------------
def main():
    print("=== Поля і каміння — пошук довгого простого шляху (забезпечує, що фініт останній) ===")
    try:
        N = int(input("Введіть кількість рядків N (1..100): ").strip())
        M = int(input("Введіть кількість стовпців M (1..100): ").strip())
    except Exception:
        print("Некоректні N або M.")
        return
    if not (1 <= N <= 100 and 1 <= M <= 100):
        print("N і M повинні бути від 1 до 100.")
        return

    try:
        p = float(input("Ймовірність каменю в клітинці (0..1), наприклад 0.25: ").strip())
        if not (0.0 <= p <= 1.0):
            raise ValueError()
    except Exception:
        print("Некоректне p — використовую 0.25")
        p = 0.25

    try:
        tlim = float(input("Часовий ліміт пошуку в секундах (наприклад 1.5): ").strip())
        if tlim <= 0:
            tlim = 1.5
    except Exception:
        tlim = 1.5

    regen = input("Якщо потрібно — регенерувати поле поки існує шлях? (т/н) [т]: ").strip().lower()
    regen_flag = (regen == "" or regen == "т" or regen == "y" or regen == "yes")

    attempts = 0
    while True:
        attempts += 1
        grid = generate_field(N, M, p)
        if exists_path_bfs(grid):
            break
        if not regen_flag:
            break
        if attempts > 2000:
            print("Не вдалось згенерувати поле з шляхом за багато спроб. Спробуйте змінити p.")
            return

    print("\nЗгенероване поле (вирівняне):")
    print_board_numbered(grid, None)

    if not exists_path_bfs(grid):
        print("Шляху немає — завершую.")
        return

    print(f"Починаємо пошук найдовшого простого шляху (таймаут = {tlim} сек)...")
    best = longest_path_dfs(grid, time_limit=tlim, randomize=True)

    if not best:
        print("Не знайдено жодного шляху (неочікувано).")
        return

    # best — шлях з старту до фінішу, простий, goal останній
    print(f"Знайдений шлях довжиною {len(best)} (0 = старт).")
    print("\nКарта з пронумерованим шляхом:")
    print_board_numbered(grid, best)

    # Додатково: виведемо координати шляху у 1-based
    print("\nКроки шляху (1-based координати):")
    print([(r+1, c+1) for (r,c) in best])

if __name__ == "__main__":
    main()