fork download 
  1. import random
  2. import time
  3. import sys
  4.  
  5. sys.setrecursionlimit(10000)
  6.  
  7. # ------------------------
  8. # Генерація поля
  9. # 0 = поле ('.'), 1 = камінь ('#')
  10. # ------------------------
  11. def generate_field(N, M, p):
  12.     grid = [[1 if random.random() < p else 0 for _ in range(M)] for _ in range(N)]
  13.     grid[N-1][0] = 0 
  14.     grid[0][M-1] = 0 
  15.     return grid
  16.  
  17.  
  18. from collections import deque
  19. def exists_path_bfs(grid):
  20.     N, M = len(grid), len(grid[0])
  21.     start = (N-1,0)
  22.     goal = (0, M-1)
  23.     if grid[start[0]][start[1]] != 0 or grid[goal[0]][goal[1]] != 0:
  24.         return False
  25.     q = deque([start])
  26.     vis = [[False]*M for _ in range(N)]
  27.     vis[start[0]][start[1]] = True
  28.     dirs = [(1,0),(-1,0),(0,1),(0,-1)]
  29.     while q:
  30.         r,c = q.popleft()
  31.         if (r,c) == goal:
  32.             return True
  33.         for dr,dc in dirs:
  34.             nr, nc = r+dr, c+dc
  35.             if 0 <= nr < N and 0 <= nc < M and not vis[nr][nc] and grid[nr][nc] == 0:
  36.                 vis[nr][nc] = True
  37.                 q.append((nr,nc))
  38.     return False
  39.  
  40. def longest_path_dfs(grid, time_limit=1.5, randomize=True):
  41.     N, M = len(grid), len(grid[0])
  42.     start = (N-1, 0)
  43.     goal = (0, M-1)
  44.     dirs = [(1,0), (0,1), (-1,0), (0,-1)]  
  45.     best_path = None
  46.     best_len = -1
  47.     start_time = time.time()
  48.     max_nodes = 10**6
  49.     nodes = 0
  50.  
  51.     import random as _rnd
  52.  
  53.     visited = [[False]*M for _ in range(N)]
  54.     path = []
  55.  
  56.     def dfs(r,c):
  57.         nonlocal best_len, best_path, nodes
  58.         if time.time() - start_time > time_limit:
  59.             return
  60.         nodes += 1
  61.         if nodes > max_nodes:
  62.             return
  63.  
  64.         if (r,c) == goal:
  65.             if len(path) > best_len:
  66.                 best_len = len(path)
  67.                 best_path = path.copy()
  68.             return
  69.  
  70.         neighs = []
  71.         for dr,dc in dirs:
  72.             nr, nc = r+dr, c+dc
  73.             if 0 <= nr < N and 0 <= nc < M and not visited[nr][nc] and grid[nr][nc] == 0:
  74.                 dist = abs(nr - goal[0]) + abs(nc - goal[1])
  75.                 neighs.append((dist, nr, nc))
  76.         neighs.sort(reverse=True, key=lambda x: x[0])
  77.         if randomize:
  78.             i = 0
  79.             while i < len(neighs):
  80.                 j = i
  81.                 while j < len(neighs) and neighs[j][0] == neighs[i][0]:
  82.                     j += 1
  83.                 block = neighs[i:j]
  84.                 _rnd.shuffle(block)
  85.                 neighs[i:j] = block
  86.                 i = j
  87.  
  88.         for _, nr, nc in neighs:
  89.             if time.time() - start_time > time_limit:
  90.                 return
  91.             visited[nr][nc] = True
  92.             path.append((nr,nc))
  93.             dfs(nr,nc)
  94.             path.pop()
  95.             visited[nr][nc] = False
  96.     if grid[start[0]][start[1]] != 0 or grid[goal[0]][goal[1]] != 0:
  97.         return None
  98.  
  99.     visited[start[0]][start[1]] = True
  100.     path.append(start)
  101.     dfs(start[0], start[1])
  102.     visited[start[0]][start[1]] = False
  103.     path.pop()
  104.  
  105.     return best_path
  106.  
  107. def print_board_numbered(grid, path):
  108.     N, M = len(grid), len(grid[0])
  109.     step = {}
  110.     if path:
  111.         for i, cell in enumerate(path):
  112.             step[cell] = i
  113.  
  114.     max_step = max(step.values()) if step else 0
  115.     width = max(3, len(str(max_step)) + 2)
  116.  
  117.     def cell_str(s):
  118.         return str(s).center(width)
  119.  
  120.     print()
  121.     for r in range(N):
  122.         row_cells = []
  123.         for c in range(M):
  124.             if (r,c) in step:
  125.                 row_cells.append(cell_str(step[(r,c)]))
  126.             elif grid[r][c] == 1:
  127.                 row_cells.append(cell_str("#"))
  128.             else:
  129.                 row_cells.append(cell_str("."))
  130.         print("".join(row_cells))
  131.     print()
  132. def main():
  133.     print("=== Поля і каміння — пошук довгого простого шляху")
  134.     try:
  135.         N = int(input("Введіть кількість рядків N (1..100): ").strip())
  136.         M = int(input("Введіть кількість стовпців M (1..100): ").strip())
  137.     except Exception:
  138.         print("Некоректні N або M.")
  139.         return
  140.     if not (1 <= N <= 100 and 1 <= M <= 100):
  141.         print("N і M повинні бути від 1 до 100.")
  142.         return
  143.  
  144.     try:
  145.         p = float(input("Ймовірність каменю в клітинці (0..1), наприклад 0.25: ").strip())
  146.         if not (0.0 <= p <= 1.0):
  147.             raise ValueError()
  148.     except Exception:
  149.         print("Некоректне p — використовую 0.25")
  150.         p = 0.25
  151.  
  152.     try:
  153.         tlim = float(input("Часовий ліміт пошуку в секундах (наприклад 1.5): ").strip())
  154.         if tlim <= 0:
  155.             tlim = 1.5
  156.     except Exception:
  157.         tlim = 1.5
  158.  
  159.     regen = input("Якщо потрібно — згенерувати поле заново, якщо шляху немає? (т/н) [т]: ").strip().lower()
  160.     regen_flag = (regen == "" or regen == "т" or regen == "y" or regen == "yes")
  161.  
  162.     attempts = 0
  163.     while True:
  164.         attempts += 1
  165.         grid = generate_field(N, M, p)
  166.         if exists_path_bfs(grid):
  167.             break
  168.         if not regen_flag:
  169.             break
  170.         if attempts > 2000:
  171.             print("Не вдалось згенерувати поле з шляхом за багато спроб. Спробуйте змінити p.")
  172.             return
  173.  
  174.     print("\nЗгенероване поле (вирівняне):")
  175.     print_board_numbered(grid, None)
  176.  
  177.     if not exists_path_bfs(grid):
  178.         print("Шляху немає — завершую.")
  179.         return
  180.  
  181.     print(f"Починаємо пошук найдовшого простого шляху (таймаут = {tlim} сек)...")
  182.     best = longest_path_dfs(grid, time_limit=tlim, randomize=True)
  183.  
  184.     if not best:
  185.         print("Не знайдено жодного шляху (неочікувано).")
  186.         return
  187.  
  188.     print(f"Знайдений шлях довжиною {len(best)} (0 = старт).")
  189.     print("\nКарта з пронумерованим шляхом:")
  190.     print_board_numbered(grid, best)
  191.  
  192.     print("\nКроки шляху (1-based координати):")
  193.     print([(r+1, c+1) for (r,c) in best])
  194.  
  195. if __name__ == "__main__":
  196.     main()
  197.  
Success #stdin #stdout 1.59s 14384KB
comments (?)
stdin 
25
25
0.25
1.5
т
stdout 
=== Поля і каміння — пошук довгого простого шляху
Введіть кількість рядків N (1..100): Введіть кількість стовпців M (1..100): Ймовірність каменю в клітинці (0..1), наприклад 0.25: Часовий ліміт пошуку в секундах (наприклад 1.5): Якщо потрібно — згенерувати поле заново, якщо шляху немає? (т/н) [т]: 
Згенероване поле (вирівняне):

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

Починаємо пошук найдовшого простого шляху (таймаут = 1.5 сек)...
Не знайдено жодного шляху (неочікувано).
https://ideone.com/mQUNRN
language:
Python 3 (python  3.12)
created:
1 day ago
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!