Ideone.com

fork download

copy

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
 
 
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
 
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
 
        if (r,c) == goal:
            if len(path) > best_len:
                best_len = len(path)
                best_path = path.copy()
            return
 
        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:
                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
                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
    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])
    visited[start[0]][start[1]] = False
    path.pop()
 
    return best_path
 
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()
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
 
    print(f"Знайдений шлях довжиною {len(best)} (0 = старт).")
    print("\nКарта з пронумерованим шляхом:")
    print_board_numbered(grid, best)
 
    print("\nКроки шляху (1-based координати):")
    print([(r+1, c+1) for (r,c) in best])
 
if __name__ == "__main__":
    main()

aW1wb3J0IHJhbmRvbQppbXBvcnQgdGltZQppbXBvcnQgc3lzCgpzeXMuc2V0cmVjdXJzaW9ubGltaXQoMTAwMDApCgojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQojINCT0LXQvdC10YDQsNGG0ZbRjyDQv9C+0LvRjwojIDAgPSDQv9C+0LvQtSAoJy4nKSwgMSA9INC60LDQvNGW0L3RjCAoJyMnKQojIC0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQpkZWYgZ2VuZXJhdGVfZmllbGQoTiwgTSwgcCk6CiAgICBncmlkID0gW1sxIGlmIHJhbmRvbS5yYW5kb20oKSA8IHAgZWxzZSAwIGZvciBfIGluIHJhbmdlKE0pXSBmb3IgXyBpbiByYW5nZShOKV0KICAgIGdyaWRbTi0xXVswXSA9IDAgCiAgICBncmlkWzBdW00tMV0gPSAwIAogICAgcmV0dXJuIGdyaWQKCgpmcm9tIGNvbGxlY3Rpb25zIGltcG9ydCBkZXF1ZQpkZWYgZXhpc3RzX3BhdGhfYmZzKGdyaWQpOgogICAgTiwgTSA9IGxlbihncmlkKSwgbGVuKGdyaWRbMF0pCiAgICBzdGFydCA9IChOLTEsMCkKICAgIGdvYWwgPSAoMCwgTS0xKQogICAgaWYgZ3JpZFtzdGFydFswXV1bc3RhcnRbMV1dICE9IDAgb3IgZ3JpZFtnb2FsWzBdXVtnb2FsWzFdXSAhPSAwOgogICAgICAgIHJldHVybiBGYWxzZQogICAgcSA9IGRlcXVlKFtzdGFydF0pCiAgICB2aXMgPSBbW0ZhbHNlXSpNIGZvciBfIGluIHJhbmdlKE4pXQogICAgdmlzW3N0YXJ0WzBdXVtzdGFydFsxXV0gPSBUcnVlCiAgICBkaXJzID0gWygxLDApLCgtMSwwKSwoMCwxKSwoMCwtMSldCiAgICB3aGlsZSBxOgogICAgICAgIHIsYyA9IHEucG9wbGVmdCgpCiAgICAgICAgaWYgKHIsYykgPT0gZ29hbDoKICAgICAgICAgICAgcmV0dXJuIFRydWUKICAgICAgICBmb3IgZHIsZGMgaW4gZGlyczoKICAgICAgICAgICAgbnIsIG5jID0gcitkciwgYytkYwogICAgICAgICAgICBpZiAwIDw9IG5yIDwgTiBhbmQgMCA8PSBuYyA8IE0gYW5kIG5vdCB2aXNbbnJdW25jXSBhbmQgZ3JpZFtucl1bbmNdID09IDA6CiAgICAgICAgICAgICAgICB2aXNbbnJdW25jXSA9IFRydWUKICAgICAgICAgICAgICAgIHEuYXBwZW5kKChucixuYykpCiAgICByZXR1cm4gRmFsc2UKCmRlZiBsb25nZXN0X3BhdGhfZGZzKGdyaWQsIHRpbWVfbGltaXQ9MS41LCByYW5kb21pemU9VHJ1ZSk6CiAgICBOLCBNID0gbGVuKGdyaWQpLCBsZW4oZ3JpZFswXSkKICAgIHN0YXJ0ID0gKE4tMSwgMCkKICAgIGdvYWwgPSAoMCwgTS0xKQogICAgZGlycyA9IFsoMSwwKSwgKDAsMSksICgtMSwwKSwgKDAsLTEpXSAgCiAgICBiZXN0X3BhdGggPSBOb25lCiAgICBiZXN0X2xlbiA9IC0xCiAgICBzdGFydF90aW1lID0gdGltZS50aW1lKCkKICAgIG1heF9ub2RlcyA9IDEwKio2CiAgICBub2RlcyA9IDAKCiAgICBpbXBvcnQgcmFuZG9tIGFzIF9ybmQKCiAgICB2aXNpdGVkID0gW1tGYWxzZV0qTSBmb3IgXyBpbiByYW5nZShOKV0KICAgIHBhdGggPSBbXQoKICAgIGRlZiBkZnMocixjKToKICAgICAgICBub25sb2NhbCBiZXN0X2xlbiwgYmVzdF9wYXRoLCBub2RlcwogICAgICAgIGlmIHRpbWUudGltZSgpIC0gc3RhcnRfdGltZSA+IHRpbWVfbGltaXQ6CiAgICAgICAgICAgIHJldHVybgogICAgICAgIG5vZGVzICs9IDEKICAgICAgICBpZiBub2RlcyA+IG1heF9ub2RlczoKICAgICAgICAgICAgcmV0dXJuCgogICAgICAgIGlmIChyLGMpID09IGdvYWw6CiAgICAgICAgICAgIGlmIGxlbihwYXRoKSA+IGJlc3RfbGVuOgogICAgICAgICAgICAgICAgYmVzdF9sZW4gPSBsZW4ocGF0aCkKICAgICAgICAgICAgICAgIGJlc3RfcGF0aCA9IHBhdGguY29weSgpCiAgICAgICAgICAgIHJldHVybgoKICAgICAgICBuZWlnaHMgPSBbXQogICAgICAgIGZvciBkcixkYyBpbiBkaXJzOgogICAgICAgICAgICBuciwgbmMgPSByK2RyLCBjK2RjCiAgICAgICAgICAgIGlmIDAgPD0gbnIgPCBOIGFuZCAwIDw9IG5jIDwgTSBhbmQgbm90IHZpc2l0ZWRbbnJdW25jXSBhbmQgZ3JpZFtucl1bbmNdID09IDA6CiAgICAgICAgICAgICAgICBkaXN0ID0gYWJzKG5yIC0gZ29hbFswXSkgKyBhYnMobmMgLSBnb2FsWzFdKQogICAgICAgICAgICAgICAgbmVpZ2hzLmFwcGVuZCgoZGlzdCwgbnIsIG5jKSkKICAgICAgICBuZWlnaHMuc29ydChyZXZlcnNlPVRydWUsIGtleT1sYW1iZGEgeDogeFswXSkKICAgICAgICBpZiByYW5kb21pemU6CiAgICAgICAgICAgIGkgPSAwCiAgICAgICAgICAgIHdoaWxlIGkgPCBsZW4obmVpZ2hzKToKICAgICAgICAgICAgICAgIGogPSBpCiAgICAgICAgICAgICAgICB3aGlsZSBqIDwgbGVuKG5laWdocykgYW5kIG5laWdoc1tqXVswXSA9PSBuZWlnaHNbaV1bMF06CiAgICAgICAgICAgICAgICAgICAgaiArPSAxCiAgICAgICAgICAgICAgICBibG9jayA9IG5laWdoc1tpOmpdCiAgICAgICAgICAgICAgICBfcm5kLnNodWZmbGUoYmxvY2spCiAgICAgICAgICAgICAgICBuZWlnaHNbaTpqXSA9IGJsb2NrCiAgICAgICAgICAgICAgICBpID0gagoKICAgICAgICBmb3IgXywgbnIsIG5jIGluIG5laWdoczoKICAgICAgICAgICAgaWYgdGltZS50aW1lKCkgLSBzdGFydF90aW1lID4gdGltZV9saW1pdDoKICAgICAgICAgICAgICAgIHJldHVybgogICAgICAgICAgICB2aXNpdGVkW25yXVtuY10gPSBUcnVlCiAgICAgICAgICAgIHBhdGguYXBwZW5kKChucixuYykpCiAgICAgICAgICAgIGRmcyhucixuYykKICAgICAgICAgICAgcGF0aC5wb3AoKQogICAgICAgICAgICB2aXNpdGVkW25yXVtuY10gPSBGYWxzZQogICAgaWYgZ3JpZFtzdGFydFswXV1bc3RhcnRbMV1dICE9IDAgb3IgZ3JpZFtnb2FsWzBdXVtnb2FsWzFdXSAhPSAwOgogICAgICAgIHJldHVybiBOb25lCgogICAgdmlzaXRlZFtzdGFydFswXV1bc3RhcnRbMV1dID0gVHJ1ZQogICAgcGF0aC5hcHBlbmQoc3RhcnQpCiAgICBkZnMoc3RhcnRbMF0sIHN0YXJ0WzFdKQogICAgdmlzaXRlZFtzdGFydFswXV1bc3RhcnRbMV1dID0gRmFsc2UKICAgIHBhdGgucG9wKCkKCiAgICByZXR1cm4gYmVzdF9wYXRoCgpkZWYgcHJpbnRfYm9hcmRfbnVtYmVyZWQoZ3JpZCwgcGF0aCk6CiAgICBOLCBNID0gbGVuKGdyaWQpLCBsZW4oZ3JpZFswXSkKICAgIHN0ZXAgPSB7fQogICAgaWYgcGF0aDoKICAgICAgICBmb3IgaSwgY2VsbCBpbiBlbnVtZXJhdGUocGF0aCk6CiAgICAgICAgICAgIHN0ZXBbY2VsbF0gPSBpCgogICAgbWF4X3N0ZXAgPSBtYXgoc3RlcC52YWx1ZXMoKSkgaWYgc3RlcCBlbHNlIDAKICAgIHdpZHRoID0gbWF4KDMsIGxlbihzdHIobWF4X3N0ZXApKSArIDIpCgogICAgZGVmIGNlbGxfc3RyKHMpOgogICAgICAgIHJldHVybiBzdHIocykuY2VudGVyKHdpZHRoKQoKICAgIHByaW50KCkKICAgIGZvciByIGluIHJhbmdlKE4pOgogICAgICAgIHJvd19jZWxscyA9IFtdCiAgICAgICAgZm9yIGMgaW4gcmFuZ2UoTSk6CiAgICAgICAgICAgIGlmIChyLGMpIGluIHN0ZXA6CiAgICAgICAgICAgICAgICByb3dfY2VsbHMuYXBwZW5kKGNlbGxfc3RyKHN0ZXBbKHIsYyldKSkKICAgICAgICAgICAgZWxpZiBncmlkW3JdW2NdID09IDE6CiAgICAgICAgICAgICAgICByb3dfY2VsbHMuYXBwZW5kKGNlbGxfc3RyKCIjIikpCiAgICAgICAgICAgIGVsc2U6CiAgICAgICAgICAgICAgICByb3dfY2VsbHMuYXBwZW5kKGNlbGxfc3RyKCIuIikpCiAgICAgICAgcHJpbnQoIiIuam9pbihyb3dfY2VsbHMpKQogICAgcHJpbnQoKQpkZWYgbWFpbigpOgogICAgcHJpbnQoIj09PSDQn9C+0LvRjyDRliDQutCw0LzRltC90L3RjyDigJQg0L/QvtGI0YPQuiDQtNC+0LLQs9C+0LPQviDQv9GA0L7RgdGC0L7Qs9C+INGI0LvRj9GF0YMgKNC30LDQsdC10LfQv9C10YfRg9GULCDRidC+INGE0ZbQvdGW0YIg0L7RgdGC0LDQvdC90ZbQuSkgPT09IikKICAgIHRyeToKICAgICAgICBOID0gaW50KGlucHV0KCLQktCy0LXQtNGW0YLRjCDQutGW0LvRjNC60ZbRgdGC0Ywg0YDRj9C00LrRltCyIE4gKDEuLjEwMCk6ICIpLnN0cmlwKCkpCiAgICAgICAgTSA9IGludChpbnB1dCgi0JLQstC10LTRltGC0Ywg0LrRltC70YzQutGW0YHRgtGMINGB0YLQvtCy0L/RhtGW0LIgTSAoMS4uMTAwKTogIikuc3RyaXAoKSkKICAgIGV4Y2VwdCBFeGNlcHRpb246CiAgICAgICAgcHJpbnQoItCd0LXQutC+0YDQtdC60YLQvdGWIE4g0LDQsdC+IE0uIikKICAgICAgICByZXR1cm4KICAgIGlmIG5vdCAoMSA8PSBOIDw9IDEwMCBhbmQgMSA8PSBNIDw9IDEwMCk6CiAgICAgICAgcHJpbnQoIk4g0ZYgTSDQv9C+0LLQuNC90L3RliDQsdGD0YLQuCDQstGW0LQgMSDQtNC+IDEwMC4iKQogICAgICAgIHJldHVybgoKICAgIHRyeToKICAgICAgICBwID0gZmxvYXQoaW5wdXQoItCZ0LzQvtCy0ZbRgNC90ZbRgdGC0Ywg0LrQsNC80LXQvdGOINCyINC60LvRltGC0LjQvdGG0ZYgKDAuLjEpLCDQvdCw0L/RgNC40LrQu9Cw0LQgMC4yNTogIikuc3RyaXAoKSkKICAgICAgICBpZiBub3QgKDAuMCA8PSBwIDw9IDEuMCk6CiAgICAgICAgICAgIHJhaXNlIFZhbHVlRXJyb3IoKQogICAgZXhjZXB0IEV4Y2VwdGlvbjoKICAgICAgICBwcmludCgi0J3QtdC60L7RgNC10LrRgtC90LUgcCDigJQg0LLQuNC60L7RgNC40YHRgtC+0LLRg9GOIDAuMjUiKQogICAgICAgIHAgPSAwLjI1CgogICAgdHJ5OgogICAgICAgIHRsaW0gPSBmbG9hdChpbnB1dCgi0KfQsNGB0L7QstC40Lkg0LvRltC80ZbRgiDQv9C+0YjRg9C60YMg0LIg0YHQtdC60YPQvdC00LDRhSAo0L3QsNC/0YDQuNC60LvQsNC0IDEuNSk6ICIpLnN0cmlwKCkpCiAgICAgICAgaWYgdGxpbSA8PSAwOgogICAgICAgICAgICB0bGltID0gMS41CiAgICBleGNlcHQgRXhjZXB0aW9uOgogICAgICAgIHRsaW0gPSAxLjUKCiAgICByZWdlbiA9IGlucHV0KCLQr9C60YnQviDQv9C+0YLRgNGW0LHQvdC+IOKAlCDQt9Cz0LXQvdC10YDRg9Cy0LDRgtC4INC/0L7Qu9C1INC30LDQvdC+0LLQviwg0Y/QutGJ0L4g0YjQu9GP0YXRgyDQvdC10LzQsNGUPyAo0YIv0L0pIFvRgl06ICIpLnN0cmlwKCkubG93ZXIoKQogICAgcmVnZW5fZmxhZyA9IChyZWdlbiA9PSAiIiBvciByZWdlbiA9PSAi0YIiIG9yIHJlZ2VuID09ICJ5IiBvciByZWdlbiA9PSAieWVzIikKCiAgICBhdHRlbXB0cyA9IDAKICAgIHdoaWxlIFRydWU6CiAgICAgICAgYXR0ZW1wdHMgKz0gMQogICAgICAgIGdyaWQgPSBnZW5lcmF0ZV9maWVsZChOLCBNLCBwKQogICAgICAgIGlmIGV4aXN0c19wYXRoX2JmcyhncmlkKToKICAgICAgICAgICAgYnJlYWsKICAgICAgICBpZiBub3QgcmVnZW5fZmxhZzoKICAgICAgICAgICAgYnJlYWsKICAgICAgICBpZiBhdHRlbXB0cyA+IDIwMDA6CiAgICAgICAgICAgIHByaW50KCLQndC1INCy0LTQsNC70L7RgdGMINC30LPQtdC90LXRgNGD0LLQsNGC0Lgg0L/QvtC70LUg0Lcg0YjQu9GP0YXQvtC8INC30LAg0LHQsNCz0LDRgtC+INGB0L/RgNC+0LEuINCh0L/RgNC+0LHRg9C50YLQtSDQt9C80ZbQvdC40YLQuCBwLiIpCiAgICAgICAgICAgIHJldHVybgoKICAgIHByaW50KCJcbtCX0LPQtdC90LXRgNC+0LLQsNC90LUg0L/QvtC70LUgKNCy0LjRgNGW0LLQvdGP0L3QtSk6IikKICAgIHByaW50X2JvYXJkX251bWJlcmVkKGdyaWQsIE5vbmUpCgogICAgaWYgbm90IGV4aXN0c19wYXRoX2JmcyhncmlkKToKICAgICAgICBwcmludCgi0KjQu9GP0YXRgyDQvdC10LzQsNGUIOKAlCDQt9Cw0LLQtdGA0YjRg9GOLiIpCiAgICAgICAgcmV0dXJuCgogICAgcHJpbnQoZiLQn9C+0YfQuNC90LDRlNC80L4g0L/QvtGI0YPQuiDQvdCw0LnQtNC+0LLRiNC+0LPQviDQv9GA0L7RgdGC0L7Qs9C+INGI0LvRj9GF0YMgKNGC0LDQudC80LDRg9GCID0ge3RsaW19INGB0LXQuikuLi4iKQogICAgYmVzdCA9IGxvbmdlc3RfcGF0aF9kZnMoZ3JpZCwgdGltZV9saW1pdD10bGltLCByYW5kb21pemU9VHJ1ZSkKCiAgICBpZiBub3QgYmVzdDoKICAgICAgICBwcmludCgi0J3QtSDQt9C90LDQudC00LXQvdC+INC20L7QtNC90L7Qs9C+INGI0LvRj9GF0YMgKNC90LXQvtGH0ZbQutGD0LLQsNC90L4pLiIpCiAgICAgICAgcmV0dXJuCgogICAgcHJpbnQoZiLQl9C90LDQudC00LXQvdC40Lkg0YjQu9GP0YUg0LTQvtCy0LbQuNC90L7RjiB7bGVuKGJlc3QpfSAoMCA9INGB0YLQsNGA0YIpLiIpCiAgICBwcmludCgiXG7QmtCw0YDRgtCwINC3INC/0YDQvtC90YPQvNC10YDQvtCy0LDQvdC40Lwg0YjQu9GP0YXQvtC8OiIpCiAgICBwcmludF9ib2FyZF9udW1iZXJlZChncmlkLCBiZXN0KQoKICAgIHByaW50KCJcbtCa0YDQvtC60Lgg0YjQu9GP0YXRgyAoMS1iYXNlZCDQutC+0L7RgNC00LjQvdCw0YLQuCk6IikKICAgIHByaW50KFsocisxLCBjKzEpIGZvciAocixjKSBpbiBiZXN0XSkKCmlmIF9fbmFtZV9fID09ICJfX21haW5fXyI6CiAgICBtYWluKCkK

Success #stdin #stdout 1.6s 14340KB

stdin

copy

stdout

copy

=== Поля і каміння — пошук довгого простого шляху (забезпечує, що фініт останній) ===
Введіть кількість рядків N (1..100): Введіть кількість стовпців M (1..100): Ймовірність каменю в клітинці (0..1), наприклад 0.25: Часовий ліміт пошуку в секундах (наприклад 1.5): Якщо потрібно — згенерувати поле заново, якщо шляху немає? (т/н) [т]: 
Згенероване поле (вирівняне):

 .  #  #  .  .  .  .  .  .  .  #  #  .  .  .  .  .  .  #  .  .  .  .  .  . 
 .  .  .  .  .  .  .  .  .  .  .  #  #  .  .  .  .  #  #  #  .  .  .  .  . 
 .  .  .  .  .  .  .  .  .  #  .  .  .  .  .  .  .  #  .  .  .  .  #  .  . 
 .  .  #  .  .  .  .  .  #  .  #  .  .  .  .  .  .  .  .  .  .  .  .  .  # 
 #  #  .  .  .  .  .  #  .  #  #  .  .  .  .  .  .  .  .  #  #  .  .  .  . 
 .  .  #  .  .  #  .  .  .  .  .  #  #  #  #  .  .  #  .  .  .  .  #  .  . 
 .  .  .  .  .  #  .  .  .  .  #  .  #  .  .  .  .  #  .  #  .  .  .  .  . 
 .  .  .  .  .  .  .  .  .  .  .  .  #  #  #  .  .  .  .  #  .  .  .  .  . 
 #  .  .  .  .  .  .  #  .  #  .  #  .  #  .  .  .  .  .  .  #  .  .  .  . 
 .  .  #  .  #  .  .  .  #  .  .  .  .  .  #  .  .  .  #  .  .  .  #  .  # 
 .  .  #  .  #  .  .  #  .  #  .  .  .  .  .  .  .  .  .  .  .  #  .  .  . 
 .  .  .  .  .  .  #  .  .  #  .  .  .  .  .  .  #  .  .  .  .  #  .  .  . 
 #  .  .  .  .  .  #  .  .  .  .  .  #  .  .  .  .  .  .  .  #  .  .  .  . 
 .  .  #  .  .  .  .  .  #  .  .  .  .  .  .  .  .  .  #  .  .  .  .  #  . 
 .  .  .  #  .  .  .  #  .  .  #  .  .  .  .  .  .  #  .  .  #  .  .  .  # 
 .  #  .  .  .  .  .  .  #  .  .  .  .  #  .  #  .  .  .  #  #  .  .  .  . 
 .  #  .  #  .  #  #  .  .  .  .  .  .  .  .  .  .  .  #  .  .  #  .  #  . 
 .  .  #  #  #  .  #  .  .  .  #  #  .  .  #  .  .  .  .  .  #  .  .  .  . 
 .  .  .  .  #  .  .  .  .  .  .  .  .  #  #  .  .  .  .  #  .  .  .  .  # 
 .  #  .  .  .  .  .  #  .  #  #  .  .  .  #  .  #  #  #  .  .  .  #  .  . 
 .  .  .  .  .  .  .  #  .  .  .  .  .  .  .  #  #  .  .  .  #  .  .  .  # 
 #  #  .  .  .  #  .  #  .  .  .  .  .  .  #  .  #  .  .  .  .  .  .  .  . 
 .  .  .  #  .  #  .  #  .  .  .  .  .  .  .  #  #  #  .  .  .  .  #  .  . 
 #  .  .  .  .  .  .  .  .  .  .  .  .  #  .  .  .  #  #  #  .  #  #  .  . 
 .  .  .  .  .  .  #  .  .  .  .  .  .  .  #  .  .  #  .  .  .  .  .  .  . 

Починаємо пошук найдовшого простого шляху (таймаут = 1.5 сек)...
Знайдений шлях довжиною 357 (0 = старт).

Карта з пронумерованим шляхом:

  .    #    #    .    .    .    .    .    .    .    #    #    .   323  324  327  328   .    #    .   352  353  354  355  356 
 167  168  169  170  171   .    .    .    .    .    .    #    #   322  325  326  329   #    #    #   351  348  347  346  345 
 166  165  164  163  172  173   .    .    .    #    .   315  316  321  320  331  330   #   336  337  350  349   #   343  344 
  .    .    #   162  161  174   .    .    #    .    #   314  317  318  319  332  333  334  335  338  339  340  341  342   #  
  #    #    .   159  160  175  176   #    .    #    #   313  312  311  310  309  304  303  302   #    #   297  296  295  294 
 153  154   #   158   .    #   177   .    .    .    .    #    #    #    #   308  305   #   301  300  299  298   #   292  293 
 152  155  156  157   .    #   178   .    .    .    #    .    #    .    .   307  306   #    .    #   284  285  286  291  290 
 151  150  149  148  147   .   179  180  181  182  183   .    #    #    #   216  217  220  221   #   283  282  287  288  289 
  #    27   28   29  146  145  144   #    .    #   184   #    .    #    .   215  218  219  222  223   #   281  280  279   .  
  .    26   #    30   #   142  143   .    #    .   185  194  195  196   #   214  213   .    #   224   .    .    #   278   #  
  24   25   #    31   #   141   .    #    .    #   186  193  192  197  202  203  212  211   .   225   .    #   276  277   .  
  23   22   33   32  139  140   #    .    .    #   187  190  191  198  201  204   #   210  227  226   .    #   275  274   .  
  #    21   34   35  138  137   #   133  132  131  188  189   #   199  200  205  206  209  228  229   #    .   272  273   .  
  .    20   #    36   37  136  135  134   #   130  129  128  127  126  125  124  207  208   #   230  231  232  271   #    .  
  18   19   .    #    38   .    .    #    .    .    #   105  106  107  108  123  122   #    .    .    #   233  270  269   #  
  17   #    .    .    39   40   41   42   #   102  103  104   .    #   109   #   121  120   .    #    #   234  235  268  267 
  16   #    .    #    .    #    #    43   .   101  100   99   98   97  110  111  118  119   #    .    .    #   236   #   266 
  15   .    #    #    #    .    #    44   .    .    #    #    95   96   #   112  117  116   .    .    #   238  237  264  265 
  14   .    .    .    #    .    46   45   88   89   90   91   94   #    #   113  114  115   .    #   240  239   .   263   #  
  13   #    .    .    .    .    47   #    87   #    #    92   93   .    #    .    #    #    #   242  241   .    #   262   .  
  12   11   10   .    50   49   48   #    86   85   84   83   82   .    .    #    #    .   244  243   #   259  260  261   #  
  #    #    9    .    51   #    .    #    69   70   71   72   81   80   #    .    #    .   245   .    .   258  257  256   .  
  .    7    8    #    52   #    .    #    68   67   66   73   78   79   .    #    #    #   246  247  248   .    #   255   .  
  #    6    5    4    53   56   57   58   61   62   65   74   77   #    .    .    .    #    #    #   249   #    #   254   .  
  0    1    2    3    54   55   #    59   60   63   64   75   76   .    #    .    .    #    .    .   250  251  252  253   .  


Кроки шляху (1-based координати):
[(25, 1), (25, 2), (25, 3), (25, 4), (24, 4), (24, 3), (24, 2), (23, 2), (23, 3), (22, 3), (21, 3), (21, 2), (21, 1), (20, 1), (19, 1), (18, 1), (17, 1), (16, 1), (15, 1), (15, 2), (14, 2), (13, 2), (12, 2), (12, 1), (11, 1), (11, 2), (10, 2), (9, 2), (9, 3), (9, 4), (10, 4), (11, 4), (12, 4), (12, 3), (13, 3), (13, 4), (14, 4), (14, 5), (15, 5), (16, 5), (16, 6), (16, 7), (16, 8), (17, 8), (18, 8), (19, 8), (19, 7), (20, 7), (21, 7), (21, 6), (21, 5), (22, 5), (23, 5), (24, 5), (25, 5), (25, 6), (24, 6), (24, 7), (24, 8), (25, 8), (25, 9), (24, 9), (24, 10), (25, 10), (25, 11), (24, 11), (23, 11), (23, 10), (23, 9), (22, 9), (22, 10), (22, 11), (22, 12), (23, 12), (24, 12), (25, 12), (25, 13), (24, 13), (23, 13), (23, 14), (22, 14), (22, 13), (21, 13), (21, 12), (21, 11), (21, 10), (21, 9), (20, 9), (19, 9), (19, 10), (19, 11), (19, 12), (20, 12), (20, 13), (19, 13), (18, 13), (18, 14), (17, 14), (17, 13), (17, 12), (17, 11), (17, 10), (16, 10), (16, 11), (16, 12), (15, 12), (15, 13), (15, 14), (15, 15), (16, 15), (17, 15), (17, 16), (18, 16), (19, 16), (19, 17), (19, 18), (18, 18), (18, 17), (17, 17), (17, 18), (16, 18), (16, 17), (15, 17), (15, 16), (14, 16), (14, 15), (14, 14), (14, 13), (14, 12), (14, 11), (14, 10), (13, 10), (13, 9), (13, 8), (14, 8), (14, 7), (14, 6), (13, 6), (13, 5), (12, 5), (12, 6), (11, 6), (10, 6), (10, 7), (9, 7), (9, 6), (9, 5), (8, 5), (8, 4), (8, 3), (8, 2), (8, 1), (7, 1), (6, 1), (6, 2), (7, 2), (7, 3), (7, 4), (6, 4), (5, 4), (5, 5), (4, 5), (4, 4), (3, 4), (3, 3), (3, 2), (3, 1), (2, 1), (2, 2), (2, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 6), (5, 6), (5, 7), (6, 7), (7, 7), (8, 7), (8, 8), (8, 9), (8, 10), (8, 11), (9, 11), (10, 11), (11, 11), (12, 11), (13, 11), (13, 12), (12, 12), (12, 13), (11, 13), (11, 12), (10, 12), (10, 13), (10, 14), (11, 14), (12, 14), (13, 14), (13, 15), (12, 15), (11, 15), (11, 16), (12, 16), (13, 16), (13, 17), (14, 17), (14, 18), (13, 18), (12, 18), (11, 18), (11, 17), (10, 17), (10, 16), (9, 16), (8, 16), (8, 17), (9, 17), (9, 18), (8, 18), (8, 19), (9, 19), (9, 20), (10, 20), (11, 20), (12, 20), (12, 19), (13, 19), (13, 20), (14, 20), (14, 21), (14, 22), (15, 22), (16, 22), (16, 23), (17, 23), (18, 23), (18, 22), (19, 22), (19, 21), (20, 21), (20, 20), (21, 20), (21, 19), (22, 19), (23, 19), (23, 20), (23, 21), (24, 21), (25, 21), (25, 22), (25, 23), (25, 24), (24, 24), (23, 24), (22, 24), (22, 23), (22, 22), (21, 22), (21, 23), (21, 24), (20, 24), (19, 24), (18, 24), (18, 25), (17, 25), (16, 25), (16, 24), (15, 24), (15, 23), (14, 23), (13, 23), (13, 24), (12, 24), (12, 23), (11, 23), (11, 24), (10, 24), (9, 24), (9, 23), (9, 22), (8, 22), (8, 21), (7, 21), (7, 22), (7, 23), (8, 23), (8, 24), (8, 25), (7, 25), (7, 24), (6, 24), (6, 25), (5, 25), (5, 24), (5, 23), (5, 22), (6, 22), (6, 21), (6, 20), (6, 19), (5, 19), (5, 18), (5, 17), (6, 17), (7, 17), (7, 16), (6, 16), (5, 16), (5, 15), (5, 14), (5, 13), (5, 12), (4, 12), (3, 12), (3, 13), (4, 13), (4, 14), (4, 15), (3, 15), (3, 14), (2, 14), (1, 14), (1, 15), (2, 15), (2, 16), (1, 16), (1, 17), (2, 17), (3, 17), (3, 16), (4, 16), (4, 17), (4, 18), (4, 19), (3, 19), (3, 20), (4, 20), (4, 21), (4, 22), (4, 23), (4, 24), (3, 24), (3, 25), (2, 25), (2, 24), (2, 23), (2, 22), (3, 22), (3, 21), (2, 21), (1, 21), (1, 22), (1, 23), (1, 24), (1, 25)]

https://ideone.com/EW9edM

language:

Python 3 (python 3.12)

created:

visibility:

public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language