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

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

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

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

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


Кроки шляху (1-based координати):
[(25, 1), (25, 2), (25, 3), (24, 3), (24, 2), (24, 1), (23, 1), (23, 2), (22, 2), (22, 1), (21, 1), (20, 1), (19, 1), (19, 2), (18, 2), (18, 3), (18, 4), (19, 4), (20, 4), (21, 4), (22, 4), (23, 4), (24, 4), (25, 4), (25, 5), (24, 5), (23, 5), (23, 6), (24, 6), (24, 7), (25, 7), (25, 8), (24, 8), (24, 9), (24, 10), (23, 10), (23, 11), (24, 11), (24, 12), (23, 12), (23, 13), (23, 14), (24, 14), (25, 14), (25, 15), (24, 15), (24, 16), (25, 16), (25, 17), (24, 17), (23, 17), (23, 16), (23, 15), (22, 15), (22, 14), (21, 14), (21, 13), (21, 12), (21, 11), (21, 10), (21, 9), (21, 8), (20, 8), (20, 9), (20, 10), (19, 10), (18, 10), (18, 9), (18, 8), (18, 7), (18, 6), (18, 5), (17, 5), (16, 5), (16, 6), (17, 6), (17, 7), (16, 7), (15, 7), (15, 6), (14, 6), (14, 5), (14, 4), (14, 3), (14, 2), (13, 2), (13, 1), (12, 1), (11, 1), (10, 1), (9, 1), (8, 1), (7, 1), (6, 1), (6, 2), (7, 2), (8, 2), (8, 3), (8, 4), (9, 4), (10, 4), (11, 4), (11, 5), (12, 5), (13, 5), (13, 6), (13, 7), (13, 8), (12, 8), (12, 9), (11, 9), (11, 8), (11, 7), (11, 6), (10, 6), (9, 6), (9, 7), (9, 8), (10, 8), (10, 9), (9, 9), (9, 10), (10, 10), (10, 11), (11, 11), (12, 11), (12, 10), (13, 10), (13, 11), (14, 11), (14, 12), (15, 12), (16, 12), (16, 11), (17, 11), (18, 11), (19, 11), (20, 11), (20, 12), (20, 13), (19, 13), (19, 12), (18, 12), (18, 13), (18, 14), (19, 14), (19, 15), (18, 15), (18, 16), (17, 16), (17, 15), (17, 14), (17, 13), (16, 13), (15, 13), (15, 14), (14, 14), (14, 15), (13, 15), (13, 14), (12, 14), (12, 15), (12, 16), (13, 16), (13, 17), (13, 18), (14, 18), (15, 18), (16, 18), (17, 18), (17, 17), (18, 17), (19, 17), (20, 17), (20, 16), (21, 16), (22, 16), (22, 17), (22, 18), (23, 18), (24, 18), (24, 19), (23, 19), (22, 19), (21, 19), (21, 18), (20, 18), (20, 19), (20, 20), (19, 20), (19, 19), (19, 18), (18, 18), (18, 19), (18, 20), (18, 21), (19, 21), (20, 21), (20, 22), (21, 22), (22, 22), (23, 22), (24, 22), (25, 22), (25, 23), (25, 24), (25, 25), (24, 25), (23, 25), (23, 24), (22, 24), (22, 23), (21, 23), (20, 23), (19, 23), (19, 22), (18, 22), (17, 22), (16, 22), (16, 21), (15, 21), (15, 20), (14, 20), (14, 19), (13, 19), (12, 19), (12, 20), (11, 20), (11, 19), (10, 19), (10, 18), (9, 18), (9, 17), (9, 16), (8, 16), (8, 17), (7, 17), (7, 16), (6, 16), (5, 16), (5, 15), (4, 15), (4, 16), (4, 17), (4, 18), (5, 18), (6, 18), (7, 18), (8, 18), (8, 19), (8, 20), (8, 21), (9, 21), (10, 21), (11, 21), (11, 22), (12, 22), (13, 22), (13, 23), (14, 23), (15, 23), (16, 23), (17, 23), (18, 23), (18, 24), (19, 24), (20, 24), (21, 24), (21, 25), (20, 25), (19, 25), (18, 25), (17, 25), (17, 24), (16, 24), (15, 24), (15, 25), (14, 25), (13, 25), (13, 24), (12, 24), (12, 23), (11, 23), (11, 24), (11, 25), (10, 25), (10, 24), (10, 23), (9, 23), (9, 24), (8, 24), (7, 24), (7, 23), (7, 22), (7, 21), (7, 20), (6, 20), (6, 21), (6, 22), (5, 22), (4, 22), (4, 23), (5, 23), (6, 23), (6, 24), (6, 25), (5, 25), (5, 24), (4, 24), (3, 24), (3, 25), (2, 25), (2, 24), (2, 23), (1, 23), (1, 24), (1, 25)]
https://ideone.com/Gw88Yq
language:
Python 3 (python  3.12)
created:
6 hours 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!