from pprint import pprint
from collections import deque
n = 8
start = input("Введи початкову клітину (наприклад, 1 1): ").split()
end = input("Введи кінцеву клітину (наприклад, 8 8): ").split()
start = (int(start[0]) - 1, int(start[1]) - 1)
end = (int(end[0]) - 1, int(end[1]) - 1)
board = [[-2 for _ in range(n)] for _ in range(n)] 
board[start[0]][start[1]] = -1 
moves = [
    (2, 1), (1, 2), (-1, 2), (-2, 1),
    (-2, -1), (-1, -2), (1, -2), (2, -1)
]
queue = deque([(start[0], start[1], 0)])
while queue:
    x, y, step = queue.popleft()
    for dx, dy in moves:
        nx, ny = x + dx, y + dy
        if 0 <= nx < n and 0 <= ny < n and board[nx][ny] == -2:
            board[nx][ny] = step + 1
            queue.append((nx, ny, step + 1))
pprint(board)
 
if board[end[0]][end[1]] != -2:
    print(f"\n♞ Мінімальна кількість ходів: {board[end[0]][end[1]]}")
else:
    print("\n❌ Неможливо досягти цільову клітину (щось пішло не так)")

ZnJvbSBwcHJpbnQgaW1wb3J0IHBwcmludApmcm9tIGNvbGxlY3Rpb25zIGltcG9ydCBkZXF1ZQpuID0gOApzdGFydCA9IGlucHV0KCLQktCy0LXQtNC4INC/0L7Rh9Cw0YLQutC+0LLRgyDQutC70ZbRgtC40L3RgyAo0L3QsNC/0YDQuNC60LvQsNC0LCAxIDEpOiAiKS5zcGxpdCgpCmVuZCA9IGlucHV0KCLQktCy0LXQtNC4INC60ZbQvdGG0LXQstGDINC60LvRltGC0LjQvdGDICjQvdCw0L/RgNC40LrQu9Cw0LQsIDggOCk6ICIpLnNwbGl0KCkKc3RhcnQgPSAoaW50KHN0YXJ0WzBdKSAtIDEsIGludChzdGFydFsxXSkgLSAxKQplbmQgPSAoaW50KGVuZFswXSkgLSAxLCBpbnQoZW5kWzFdKSAtIDEpCmJvYXJkID0gW1stMiBmb3IgXyBpbiByYW5nZShuKV0gZm9yIF8gaW4gcmFuZ2UobildIApib2FyZFtzdGFydFswXV1bc3RhcnRbMV1dID0gLTEgCm1vdmVzID0gWwogICAgKDIsIDEpLCAoMSwgMiksICgtMSwgMiksICgtMiwgMSksCiAgICAoLTIsIC0xKSwgKC0xLCAtMiksICgxLCAtMiksICgyLCAtMSkKXQpxdWV1ZSA9IGRlcXVlKFsoc3RhcnRbMF0sIHN0YXJ0WzFdLCAwKV0pCndoaWxlIHF1ZXVlOgogICAgeCwgeSwgc3RlcCA9IHF1ZXVlLnBvcGxlZnQoKQogICAgZm9yIGR4LCBkeSBpbiBtb3ZlczoKICAgICAgICBueCwgbnkgPSB4ICsgZHgsIHkgKyBkeQogICAgICAgIGlmIDAgPD0gbnggPCBuIGFuZCAwIDw9IG55IDwgbiBhbmQgYm9hcmRbbnhdW255XSA9PSAtMjoKICAgICAgICAgICAgYm9hcmRbbnhdW255XSA9IHN0ZXAgKyAxCiAgICAgICAgICAgIHF1ZXVlLmFwcGVuZCgobngsIG55LCBzdGVwICsgMSkpCnBwcmludChib2FyZCkKCmlmIGJvYXJkW2VuZFswXV1bZW5kWzFdXSAhPSAtMjoKICAgIHByaW50KGYiXG7imZ4g0JzRltC90ZbQvNCw0LvRjNC90LAg0LrRltC70YzQutGW0YHRgtGMINGF0L7QtNGW0LI6IHtib2FyZFtlbmRbMF1dW2VuZFsxXV19IikKZWxzZToKICAgIHByaW50KCJcbuKdjCDQndC10LzQvtC20LvQuNCy0L4g0LTQvtGB0Y/Qs9GC0Lgg0YbRltC70YzQvtCy0YMg0LrQu9GW0YLQuNC90YMgKNGJ0L7RgdGMINC/0ZbRiNC70L4g0L3QtSDRgtCw0LopIik=

MSAxCjUgNQ==

1 1
5 5