fork download
copy 
  1. # your code goes here
  2. #0JLQsNGB0LjQu9C10L3QutC+INCQ0YDRgtC10Lwg
  3.  
  4. import random
  5. import sys
  6. from collections import deque
  7.  
  8. COLOR_RESET = "\033[0m"
  9. COLOR_RED = "\033[91m"
  10. COLOR_YELLOW = "\033[93m"
  11. COLOR_GREEN = "\033[92m"
  12. COLOR_BLUE = "\033[94m"
  13. COLOR_WHITE = "\033[97m"
  14. ARROWS = ['↑', '→', '↓', '←']
  15.  
  16. def solve_highway():
  17.     N = 20
  18.     M = 20
  19.     TREE_CHANCE = 0.25
  20.  
  21.     try:
  22.         user_input = input("Введіть макс. кількість поворотів (K) [Enter для 10]: ")
  23.         K = int(user_input) if user_input.strip() else 10
  24.     except ValueError:
  25.         print("K має бути числом.")
  26.         return
  27.  
  28.     grid = []
  29.     for _ in range(N):
  30.         row = []
  31.         for _ in range(M):
  32.             row.append(1 if random.random() < TREE_CHANCE else 0)
  33.         grid.append(row)
  34.  
  35.     dr = [-1, 0, 1, 0] 
  36.     dc = [0, 1, 0, -1]
  37.  
  38.     path_tracker = {}
  39.     min_lengths = {}
  40.     queue = deque()
  41.  
  42.     for r in range(N):
  43.         if grid[r][0] == 0:
  44.             state = (r, 0, -1, 0, 1)
  45.             queue.append(state)
  46.             min_lengths[(r, 0, -1, 0)] = 1
  47.             path_tracker[(r, 0, -1, 0)] = None
  48.  
  49.     best_end_state = None
  50.     min_found_length = float('inf')
  51.  
  52.     while queue:
  53.         r, c, last_dir, turns, length = queue.popleft()
  54.  
  55.         if length >= min_found_length:
  56.             continue
  57.  
  58.         if c == M - 1:
  59.             if length < min_found_length:
  60.                 min_found_length = length
  61.                 best_end_state = (r, c, last_dir, turns)
  62.             continue
  63.  
  64.         for next_dir in range(4):
  65.             nr, nc = r + dr[next_dir], c + dc[next_dir]
  66.  
  67.             if 0 <= nr < N and 0 <= nc < M and grid[nr][nc] == 0:
  68.                 new_turns = turns
  69.                 if last_dir != -1 and last_dir != next_dir:
  70.                     new_turns += 1
  71.  
  72.                 if new_turns > K:
  73.                     continue
  74.  
  75.                 new_length = length + 1
  76.                 new_state_key = (nr, nc, next_dir, new_turns)
  77.  
  78.                 if new_length < min_lengths.get(new_state_key, float('inf')):
  79.                     min_lengths[new_state_key] = new_length
  80.                     path_tracker[new_state_key] = (r, c, last_dir, turns)
  81.                     queue.append((nr, nc, next_dir, new_turns, new_length))
  82.  
  83.     if best_end_state is None:
  84.         print(f"\n{COLOR_RED}Неможливо прокласти шосе з {K} поворотами.{COLOR_RESET}")
  85.         path_set = set()
  86.     else:
  87.         print(f"\n{COLOR_GREEN}Шлях знайдено! Довжина: {min_found_length}{COLOR_RESET}")
  88.  
  89.         path_map = {}
  90.         curr = best_end_state
  91.         while curr is not None:
  92.             r, c, d, t = curr
  93.             path_map[(r, c)] = d
  94.             curr = path_tracker.get(curr)
  95.         path_set = set(path_map.keys())
  96.  
  97.  
  98.     print("   " + "".join([f"{i%10} " for i in range(M)])) 
  99.     print("  +" + "-" * (M * 2) + "+") 
  100.  
  101.     for r in range(N):
  102.         line = f"{r%10} |"
  103.         for c in range(M):
  104.             if (r, c) in path_set:
  105.                 direction = path_map[(r, c)]
  106.                 if direction == -1:
  107.                     symbol = "S"
  108.                     color = COLOR_RED
  109.                 elif c == M - 1:
  110.                     symbol = "F"
  111.                     color = COLOR_BLUE
  112.                 else:
  113.                     symbol = ARROWS[direction]
  114.                     color = COLOR_YELLOW
  115.  
  116.                 line += f"{color}{symbol}{COLOR_RESET} "
  117.             elif grid[r][c] == 1:
  118.  
  119.                 line += f"{COLOR_GREEN}#{COLOR_RESET} "
  120.             else:
  121.                 line += f"{COLOR_WHITE}.{COLOR_RESET} "
  122.         print(line + "|")
  123.     print("  +" + "-" * (M * 2) + "+")
  124.  
  125. if __name__ == "__main__":
  126.     solve_highway()
  127.  
Success #stdin #stdout 0.13s 14620KB
comments (?)
stdin
copy 
8
stdout
copy 
Введіть макс. кількість поворотів (K) [Enter для 10]: 
Шлях знайдено! Довжина: 22
   0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 
  +----------------------------------------+
0 |. . . . . . . # # # . . . . # . . . # . |
1 |. . . . . . . . . . . . . . # . # . . # |
2 |. # . . . # # . . . . # # . . . . . # . |
3 |. . . . . # . . . . . . . . # . . # . # |
4 |. . . . . . . # . . . . . . . # . . . . |
5 |. . . . . . # . # . . . # . . # . . . # |
6 |. # . # . . . . . . . . . # . . . . . . |
7 |. . # . # . # . # # . . . # . . . . . . |
8 |# . # . . # # # # . . . . . . . . # . . |
9 |. . . # . . . . . # . . . . . # . . . . |
0 |. . . . . # . . . . # . . . # # . . . . |
1 |. . . . # # . . # . . . # . . . # # # . |
2 |. # . . . . . . . # . . # # . # . . . # |
3 |. # . # . # . # . # . . . . . # . . . # |
4 |. . # # # . # # . . . . . . . . # . . # |
5 |# . # # . . . . . . # . . . # # # . . . |
6 |S → → → → → → → → # . . . . . # # # ↑ F |
7 |# . . # # . # # ↓ → → → → → → → → → → # |
8 |. . . . . . # . . . # # . # . . . . # . |
9 |# . . . . . # # . . . . # . # . . . . . |
  +----------------------------------------+
https://ideone.com/QO8Mne
language:
Python 3 (python  3.12)
created:
13 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!