QJp75v - Online Python3 Interpreter & Debugging Tool

from collections import deque

def string_to_coords(pos):
    col_char = pos[0]
    row_char = pos[1:]
    x = ord(col_char) - ord('a')
    y = int(row_char) - 1
    return x, y

def coords_to_string(x, y):
    col_char = chr(x + ord('a'))
    row_char = str(y + 1)
    return col_char + row_char

def get_knight_moves(x, y, N):
    moves = [
        (x + 1, y + 2), (x + 1, y - 2),
        (x - 1, y + 2), (x - 1, y - 2),
        (x + 2, y + 1), (x + 2, y - 1),
        (x - 2, y + 1), (x - 2, y - 1)
    ]
    valid_moves = []
    for nx, ny in moves:
        if 0 <= nx < N and 0 <= ny < N:
            valid_moves.append((nx, ny))
    return valid_moves

def print_all_shortest_paths(N, start_pos, end_pos):
    start_x, start_y = string_to_coords(start_pos)
    target_x, target_y = string_to_coords(end_pos)

    distances = [[-1] * N for _ in range(N)]
    distances[start_x][start_y] = 0

    queue = deque([(start_x, start_y)])

    while queue:
        cx, cy = queue.popleft()
        if cx == target_x and cy == target_y:
            break

        current_dist = distances[cx][cy]
        for nx, ny in get_knight_moves(cx, cy, N):
            if distances[nx][ny] == -1:
                distances[nx][ny] = current_dist + 1
                queue.append((nx, ny))

    if distances[target_x][target_y] == -1:
        print("Шляху не існує")
        return

    all_paths = []

    def find_paths_dfs(current_x, current_y, current_path):
        if current_x == target_x and current_y == target_y:
            all_paths.append(list(current_path))
            return

        current_dist = distances[current_x][current_y]

        for nx, ny in get_knight_moves(current_x, current_y, N):
            if distances[nx][ny] == current_dist + 1:
                current_path.append(coords_to_string(nx, ny))
                find_paths_dfs(nx, ny, current_path)
                current_path.pop()

    initial_path = [start_pos]
    find_paths_dfs(start_x, start_y, initial_path)

    print(f"Мінімальна кількість ходів: {distances[target_x][target_y]}")
    print(f"Знайдено варіантів шляху: {len(all_paths)}")
    for path in all_paths:
        print(" -> ".join(path))

N = 10000
start = "a1"
end = "d4"

print_all_shortest_paths(N, start, end)