Advertisement
serega1112

1 horse

Mar 7th, 2021
99
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.68 KB | None | 0 0
  1.  
  2. n = int(input())
  3. x1, y1 = map(int, input().split())
  4. x2, y2 = map(int, input().split())
  5.  
  6. grid = [[(0, 0)] * (n+1) for _ in range(n+1)]
  7.  
  8.  
  9. q = [(x1, y1)]
  10. grid[x1][y1] = (-1, -1)
  11. while q:
  12.     x, y = q.pop(0)
  13.     if x == x2 and y == y2:
  14.         break
  15.     for xp, yp in [(x+2, y+1), (x+2, y-1), (x-2, y+1), (x-2, y-1), (x+1, y+2), (x+1, y-2), (x-1, y+2), (x-1, y-2)]:
  16.         if 1 <= xp <= n and 1 <= yp <= n and grid[xp][yp] == (0, 0):
  17.             q.append((xp, yp))
  18.             grid[xp][yp] = (x, y)
  19.  
  20. count = 0
  21. path = [(x, y)]
  22.  
  23. while x != x1 or y != y1:
  24.     x, y = grid[x][y]
  25.     path.append((x, y))
  26.     count += 1
  27.  
  28. print(count)
  29. for x, y in path[::-1]:
  30.     print(f'{x} {y}')
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement