fork download 
  1. #0J/QsNGA0YXQvtC80LXQvdC60L4=
  2. from collections import deque
  3.  
  4.  
  5. HORSES_MOVES = [
  6.     (2, 1), (2, -1), (-2, 1), (-2, -1),
  7.     (1, 2), (1, -2), (-1, 2), (-1, -2)
  8. ]
  9.  
  10.  
  11. def under_attack_by_queen(x, y, qx, qy):
  12.     return (
  13.         x == qx or
  14.         y == qy or
  15.         abs(x - qx) == abs(y - qy)
  16.     )
  17.  
  18.  
  19. def bfs(N, horse, queen, target):
  20.     kx, ky = horse
  21.     qx, qy = queen
  22.     tx, ty = target
  23.  
  24.  
  25.     visited = [[[False, False] for _ in range(N)] for _ in range(N)]
  26.     queue = deque()
  27.  
  28.  
  29.     queue.append((kx, ky, 1, 0))
  30.     visited[kx][ky][1] = True
  31.  
  32.     while queue:
  33.         x, y, alive, dist = queue.popleft()
  34.  
  35.         if (x, y) == (tx, ty):
  36.             return dist
  37.  
  38.         for dx, dy in HORSES_MOVES:
  39.             nx, ny = x + dx, y + dy
  40.  
  41.             if not (0 <= nx < N and 0 <= ny < N):
  42.                 continue
  43.  
  44.             next_alive = alive
  45.  
  46.             if alive:
  47.  
  48.                 if (nx, ny) == (qx, qy):
  49.                     next_alive = 0
  50.                 else:
  51.  
  52.                     if under_attack_by_queen(nx, ny, qx, qy):
  53.                         continue
  54.  
  55.  
  56.             if not visited[nx][ny][next_alive]:
  57.                 visited[nx][ny][next_alive] = True
  58.                 queue.append((nx, ny, next_alive, dist + 1))
  59.  
  60.     return -1
  61.  
  62.  
  63.  
  64. if __name__ == "__main__":
  65.     N = 8
  66.     horse = (2, 1)
  67.     queen = (3, 3)
  68.     target = (7, 7)
  69.  
  70.     result = bfs(N, horse, queen, target)
  71.     print("Мінімальна кількість ходів:", result)
  72.  
Success #stdin #stdout 0.07s 14180KB
comments (?)
stdin 
Standard input is empty
stdout 
Мінімальна кількість ходів: 5
https://ideone.com/0Mj9Tf
language:
Python 3 (python  3.12)
created:
3 days 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!