fork download
copy 
  1. from collections import deque
  2.  
  3. def string_to_coords(pos):
  4.     col_char = pos[0]
  5.     row_char = pos[1:]
  6.     x = ord(col_char) - ord('a')
  7.     y = int(row_char) - 1
  8.     return x, y
  9.  
  10. def coords_to_string(x, y):
  11.     col_char = chr(x + ord('a'))
  12.     row_char = str(y + 1)
  13.     return col_char + row_char
  14.  
  15. def get_knight_moves(x, y, N):
  16.     moves = [
  17.         (x + 1, y + 2), (x + 1, y - 2),
  18.         (x - 1, y + 2), (x - 1, y - 2),
  19.         (x + 2, y + 1), (x + 2, y - 1),
  20.         (x - 2, y + 1), (x - 2, y - 1)
  21.     ]
  22.     valid_moves = []
  23.     for nx, ny in moves:
  24.         if 0 <= nx < N and 0 <= ny < N:
  25.             valid_moves.append((nx, ny))
  26.     return valid_moves
  27.  
  28. def print_all_shortest_paths(N, start_pos, end_pos):
  29.     start_x, start_y = string_to_coords(start_pos)
  30.     target_x, target_y = string_to_coords(end_pos)
  31.  
  32.     distances = [[-1] * N for _ in range(N)]
  33.     distances[start_x][start_y] = 0
  34.  
  35.     queue = deque([(start_x, start_y)])
  36.  
  37.     while queue:
  38.         cx, cy = queue.popleft()
  39.         if cx == target_x and cy == target_y:
  40.             break
  41.  
  42.         current_dist = distances[cx][cy]
  43.         for nx, ny in get_knight_moves(cx, cy, N):
  44.             if distances[nx][ny] == -1:
  45.                 distances[nx][ny] = current_dist + 1
  46.                 queue.append((nx, ny))
  47.  
  48.     if distances[target_x][target_y] == -1:
  49.         print("Шляху не існує")
  50.         return
  51.  
  52.     all_paths = []
  53.  
  54.     def find_paths_dfs(current_x, current_y, current_path):
  55.         if current_x == target_x and current_y == target_y:
  56.             all_paths.append(list(current_path))
  57.             return
  58.  
  59.         current_dist = distances[current_x][current_y]
  60.  
  61.         for nx, ny in get_knight_moves(current_x, current_y, N):
  62.             if distances[nx][ny] == current_dist + 1:
  63.                 current_path.append(coords_to_string(nx, ny))
  64.                 find_paths_dfs(nx, ny, current_path)
  65.                 current_path.pop()
  66.  
  67.     initial_path = [start_pos]
  68.     find_paths_dfs(start_x, start_y, initial_path)
  69.  
  70.     print(f"Мінімальна кількість ходів: {distances[target_x][target_y]}")
  71.     print(f"Знайдено варіантів шляху: {len(all_paths)}")
  72.     for path in all_paths:
  73.         print(" -> ".join(path))
  74.  
  75. N = 10000
  76. start = "a1"
  77. end = "d4"
  78.  
  79. print_all_shortest_paths(N, start, end)
  80.  
Success #stdin #stdout 1.8s 794408KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Мінімальна кількість ходів: 2
Знайдено варіантів шляху: 2
a1 -> b3 -> d4
a1 -> c2 -> d4
https://ideone.com/QJp75v
language:
Python 3 (python  3.12)
created:
9 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!