fork download
copy 
  1. import sys
  2. from collections import deque
  3.  
  4. def solve():
  5.     try:
  6.         input_data = sys.stdin.read().split()
  7.         if len(input_data) >= 3:
  8.             N = int(input_data[0])
  9.             start_pos = input_data[1]
  10.             end_pos = input_data[2]
  11.         else:
  12.             N = 8
  13.             start_pos = "a1"
  14.             end_pos = "d4"
  15.     except:
  16.         N = 8
  17.         start_pos = "a1"
  18.         end_pos = "d4"
  19.  
  20.     def parse(pos):
  21.         c = ord(pos[0]) - ord('a')
  22.         r = int(pos[1:]) - 1
  23.         return r, c
  24.  
  25.     def stringify(r, c):
  26.         return f"{chr(c + ord('a'))}{r + 1}"
  27.  
  28.     sx, sy = parse(start_pos)
  29.     ex, ey = parse(end_pos)
  30.  
  31.     moves = [
  32.         (2, 1), (2, -1), (-2, 1), (-2, -1),
  33.         (1, 2), (1, -2), (-1, 2), (-1, -2)
  34.     ]
  35.  
  36.     dist = [[-1] * N for _ in range(N)]
  37.     dist[sx][sy] = 0
  38.  
  39.     queue = deque([(sx, sy)])
  40.  
  41.     while queue:
  42.         x, y = queue.popleft()
  43.         if x == ex and y == ey:
  44.             break
  45.  
  46.         for dx, dy in moves:
  47.             nx, ny = x + dx, y + dy
  48.             if 0 <= nx < N and 0 <= ny < N and dist[nx][ny] == -1:
  49.                 dist[nx][ny] = dist[x][y] + 1
  50.                 queue.append((nx, ny))
  51.  
  52.     if dist[ex][ey] == -1:
  53.         print("Шляху немає")
  54.         return
  55.  
  56.     paths = []
  57.  
  58.     def backtrack(cx, cy, current_path):
  59.         if cx == sx and cy == sy:
  60.             paths.append(current_path[::-1])
  61.             return
  62.  
  63.         d = dist[cx][cy]
  64.  
  65.         for dx, dy in moves:
  66.             px, py = cx - dx, cy - dy
  67.             if 0 <= px < N and 0 <= py < N:
  68.                 if dist[px][py] == d - 1:
  69.                     backtrack(px, py, current_path + [stringify(px, py)])
  70.  
  71.     backtrack(ex, ey, [stringify(ex, ey)])
  72.  
  73.     paths.sort()
  74.  
  75.     print(f"Мінімальна кількість ходів: {dist[ex][ey]}")
  76.     print(f"Кількість варіантів: {len(paths)}")
  77.     for p in paths:
  78.         print(" - ".join(p))
  79.  
  80. if __name__ == "__main__":
  81.     solve()
Success #stdin #stdout 0.13s 14080KB
comments (?)
stdin
copy 
4 a1 b4
stdout
copy 
Мінімальна кількість ходів: 2
Кількість варіантів: 1
a1 - c2 - b4
https://ideone.com/wPpbJH
language:
Python 3 (python  3.12)
created:
5 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!