fork download
copy 
  1. from collections import deque
  2.  
  3. KNIGHT_MOVES = [(2,1),(2,-1),(-2,1),(-2,-1),(1,2),(1,-2),(-1,2),(-1,-2)]
  4.  
  5. def queen_attacks(N, qr, qc):
  6.     attacked = [[False]*N for _ in range(N)]
  7.     for r in range(N):
  8.         attacked[r][qc] = True
  9.     for c in range(N):
  10.         attacked[qr][c] = True
  11.     for dr in (-1, 1):
  12.         for dc in (-1, 1):
  13.             r, c = qr + dr, qc + dc
  14.             while 0 <= r < N and 0 <= c < N:
  15.                 attacked[r][c] = True
  16.                 r += dr
  17.                 c += dc
  18.     attacked[qr][qc] = True
  19.     return attacked
  20.  
  21. def find_knight_path(N, kr, kc, qr, qc, tr, tc):
  22.     for name, x, y in (("knight", kr, kc), ("queen", qr, qc), ("target", tr, tc)):
  23.         if not (0 <= x < N and 0 <= y < N):
  24.             raise IndexError(f"Координати {name} поза дошкою: ({x+1},{y+1}) у 1-based")
  25.  
  26.     attacked = queen_attacks(N, qr, qc)
  27.  
  28.     visited = [[[False]*2 for _ in range(N)] for __ in range(N)]
  29.     parent = {}
  30.  
  31.     start_alive = 0 if (kr == qr and kc == qc) else 1
  32.     start_state = (kr, kc, start_alive)
  33.     q = deque()
  34.     q.append((kr, kc, start_alive, 0))
  35.     visited[kr][kc][start_alive] = True
  36.     parent[start_state] = None
  37.  
  38.     while q:
  39.         r, c, alive, dist = q.popleft()
  40.         if (r, c) == (tr, tc):
  41.             path = []
  42.             st = (r, c, alive)
  43.             while st is not None:
  44.                 path.append((st[0], st[1]))
  45.                 st = parent.get(st)
  46.             path.reverse()
  47.             return path, dist
  48.  
  49.         for dr, dc in KNIGHT_MOVES:
  50.             nr, nc = r + dr, c + dc
  51.             if not (0 <= nr < N and 0 <= nc < N):
  52.                 continue
  53.  
  54.             nalive = alive
  55.             if alive == 1:
  56.                 if attacked[nr][nc] and not (nr == qr and nc == qc):
  57.                     continue
  58.                 if (nr == qr and nc == qc):
  59.                     nalive = 0
  60.  
  61.             if not visited[nr][nc][nalive]:
  62.                 visited[nr][nc][nalive] = True
  63.                 parent[(nr, nc, nalive)] = (r, c, alive)
  64.                 q.append((nr, nc, nalive, dist + 1))
  65.  
  66.     return None, -1
  67.  
  68. def draw_board(N, path, kr, kc, qr, qc, tr, tc):
  69.     board = [["." for _ in range(N)] for __ in range(N)]
  70.  
  71.     if path is not None:
  72.         for i, (r, c) in enumerate(path):
  73.             board[r][c] = str(i)
  74.  
  75.     def overlay(r, c, mark):
  76.         if board[r][c] == ".":
  77.             board[r][c] = mark
  78.         else:
  79.             board[r][c] = f"{mark}/{board[r][c]}"
  80.  
  81.     overlay(kr, kc, "S")
  82.     overlay(qr, qc, "Q")
  83.     overlay(tr, tc, "T")
  84.  
  85.     print("\nШахівниця (позиції у форматі MARK/num або num):")
  86.     for r in range(N):
  87.         row_str = ""
  88.         for c in range(N):
  89.             cell = board[r][c]
  90.             row_str += cell.center(6)
  91.         print(row_str)
  92.     print()
  93.  
  94. def main():
  95.     try:
  96.         N = int(input("Введіть N (розмір дошки, 1..100): ").strip())
  97.     except Exception:
  98.         print("Некоректне N")
  99.         return
  100.     if N < 1 or N > 100:
  101.         print("N має бути в діапазоні 1..100")
  102.         return
  103.  
  104.     def read_coord(name):
  105.         try:
  106.             s = input(f"Введіть {name} (рядок і стовпець, 1-based, через пробіл): ").strip().split()
  107.             if len(s) < 2:
  108.                 raise ValueError("Потрібні два числа")
  109.             r = int(s[0]); c = int(s[1])
  110.             return r-1, c-1
  111.         except Exception as e:
  112.             raise ValueError(f"Помилка вводу для {name}: {e}")
  113.  
  114.     try:
  115.         kr, kc = read_coord("координати коня")
  116.         qr, qc = read_coord("координати ферзя")
  117.         tr, tc = read_coord("координати цілі")
  118.     except ValueError as e:
  119.         print(e)
  120.         return
  121.  
  122.     print(f"Ви ввели (1-based): N={N}; K=({kr+1},{kc+1}); Q=({qr+1},{qc+1}); T=({tr+1},{tc+1})")
  123.  
  124.     for name, (x,y) in (("Кінь",(kr,kc)),("Ферзь",(qr,qc)),("Ціль",(tr,tc))):
  125.         if not (0 <= x < N and 0 <= y < N):
  126.             print(f"{name} має координати поза дошкою: ({x+1},{y+1})")
  127.             return
  128.  
  129.     path, moves = find_knight_path(N, kr, kc, qr, qc, tr, tc)
  130.     if moves == -1:
  131.         print("Шлях не знайдено — кінь не може дістатися до цілі з урахуванням правил.")
  132.     else:
  133.         print(f"Мінімальна кількість ходів: {moves}")
  134.         print("Шлях (0-based у tuple):")
  135.         print(path)
  136.         draw_board(N, path, kr, kc, qr, qc, tr, tc)
  137.  
  138. if __name__ == "__main__":
  139.     main()
  140.  
Success #stdin #stdout 0.08s 14164KB
comments (?)
stdin
copy 
15
12 12
10 10
11 11
stdout
copy 
Введіть N (розмір дошки, 1..100): Введіть координати коня (рядок і стовпець, 1-based, через пробіл): Введіть координати ферзя (рядок і стовпець, 1-based, через пробіл): Введіть координати цілі (рядок і стовпець, 1-based, через пробіл): Ви ввели (1-based): N=15; K=(12,12); Q=(10,10); T=(11,11)
Мінімальна кількість ходів: 6
Шлях (0-based у tuple):
[(11, 11), (13, 12), (11, 13), (10, 11), (9, 9), (11, 8), (10, 10)]

Шахівниця (позиції у форматі MARK/num або num):
  .     .     .     .     .     .     .     .     .     .     .     .     .     .     .   
  .     .     .     .     .     .     .     .     .     .     .     .     .     .     .   
  .     .     .     .     .     .     .     .     .     .     .     .     .     .     .   
  .     .     .     .     .     .     .     .     .     .     .     .     .     .     .   
  .     .     .     .     .     .     .     .     .     .     .     .     .     .     .   
  .     .     .     .     .     .     .     .     .     .     .     .     .     .     .   
  .     .     .     .     .     .     .     .     .     .     .     .     .     .     .   
  .     .     .     .     .     .     .     .     .     .     .     .     .     .     .   
  .     .     .     .     .     .     .     .     .     .     .     .     .     .     .   
  .     .     .     .     .     .     .     .     .    Q/4    .     .     .     .     .   
  .     .     .     .     .     .     .     .     .     .    T/6    3     .     .     .   
  .     .     .     .     .     .     .     .     5     .     .    S/0    .     2     .   
  .     .     .     .     .     .     .     .     .     .     .     .     .     .     .   
  .     .     .     .     .     .     .     .     .     .     .     .     1     .     .   
  .     .     .     .     .     .     .     .     .     .     .     .     .     .     .
https://ideone.com/gmUqI6
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!