Минимальное количество шагов шахматного коня, чтобы достигнуть определенной позиции на шахматной доске

[Programist_r]

Всем доброго времени суток)

У меня такой вопрос:
есть неограниченная шахматная доска,
с консоли мы вводим сколько примеров будет и сколько есть шахматных коней на доске, и их начальные точки(то есть , где они находятся), и точки к которым кони должны дойти за наименьшее количество шагов.

Вот как должно выглядеть:
2 - количество примеров
1 - количество шахматных коней
5 5 - начальная точка
5 6 - финальная точка
2 - количество шахматных коней
0 0 - начальная точка первого коня
1 0 - начальная точка второго коня
0 1 - финальная точка первого коня
1 1 - финальная точка второго коня

Ответ:
3 - ответ для первого коня
4 - ответ для второго коня


Сама проблема заключается в том, что не получается так сделать, потому что с первым набором данных всё хорошо, а со вторым не получается правильный ответ.
Если брать точки по отдельности, то ответ во втором наборе данных получается 6(3 для первого коня и 3 для второго коня).
У меня есть догадки как это решить, но не получается.

Догадка такая, что когда второй конь начинает движения он проходит такие же точки которые прошёл первый конь (второй пример) и нужно наверное прописать условия если первый конь был уже на этих позициях, то второй не может их проходить снова.

Вторая догадка,заключается в том что нужно прописать условия для доски и сделать и её неограниченной, и сделать так что бы конь мог ходит по отрицательным значениям шахматной доски.

вcё зависит от количество шахматных коней(количество которых мы вписываем с консоли)
их может быть 1 и 2 , и даже 10(просто в примере я этого не показывал)

проблема в том, что для одного коня всё работает отлично, а для двух и более не получается написать

Вот примерное фото(ниже):

Помогите пожалуйста, буду очень благодарен!!!

Вот мой код:

#include "pch.h"
#include <iostream>
#include <set>
#include <queue>
#include <climits>
using namespace std;
 
static const int N = INT_MAX / 2;
 
// все 8 возможных движений
// для шахматного коня
int row[] = { 2, 2, -2, -2, 1, 1, -1, -1 };
int col[] = { -1, 1, 1, -1, 2, -2, 2, -2 };
 
// Проверяем, верны ли (x, y) координаты шахматной доски
bool valid(int x, int y)
{
    if (x < 0 || y < 0 || x >= N || y >= N)
        return false;
 
    return true;
}
 
// алгоритм BFS
struct Node
{
    // (x, y) координаты шахматной доски
    // dist - минимальное расстояние из предварительной точки к финальной
    int x, y, dist;
 
    // Node конструктор
    Node(int x, int y, int dist = 0) : x(x), y(y), dist(dist) {}
 
     
    // оператор перегрузки < operator
    bool operator<(const Node& o) const
    {
        return x < o.x || (x == o.x && y < o.y);
    }
};
 
// Находим минимальное количество шагов, предпринятых конем
// из предварительной точки к финальной, используем BFS
int BFS(Node src, Node dest)
{
    // проверяем была ли посещена ячейка матрицы или нет
    set<Node> visited;
 
    // создаем очередь и ставим в очередь первый узел
    queue<Node> q;
    q.push(src);
 
    // запустить до тех пор, пока очередь не станет пустой
    while (!q.empty())
    {
        // извлекаем передний узел из очереди и обрабатываем его
        Node node = q.front();
        q.pop();
 
        int x = node.x;
        int y = node.y;
        int dist = node.dist;
 
        // если пункт назначения достигнут, вернуть dist
        if (x == dest.x && y == dest.y)
            return dist;
 
        // пропускаем, если местоположение посещалось раньше
        if (!visited.count(node))
        {
            // пометим текущий узел как посещенный
            visited.insert(node);
 
            // проверяем все 8 возможных движений коня
            // и ставим каждое правильное движение в очередь
            for (int i = 0; i < 8; ++i)
            {
                // Получить новую действительную позицию коня из текущей
                // позиция на шахматной доске и поставить ее в очередь,
                // очередь с расстоянием +1
                int x1 = x + row[i];
                int y1 = y + col[i];
 
                if (valid(x1, y1))
                    q.push({ x1, y1, dist + 1 });
            }
        }
    }
 
    // вернуть бесконечность, если путь не возможен
    return INT_MAX;
}
 
 
int main()
{
    // исходные координаты
    Node src = { 0, 1 };
 
    // координаты пункта назначения
    Node dest = { 1, 1 };
 
    cout << "Минимальное количество шагов :" << BFS(src, dest);
 
    return 0;
}

[Programist_r]

[CPP]int main()
{


int number_of_examples;
int number_of_horse;
int x, y;
int a, b;

Node src = { x,y };
Node dest = { a,b };


cin >> number_of_examples; //Число примеров

for (int i = 1; i <= number_of_examples; i++)
{
cin >> number_of_horse; //Число коней

for (int i = 1; i <= number_of_horse; i++)
{
cin >> x >> y; //Вписываем исходные координаты

}

for (int i = 1; i <= number_of_horse; i++)
{
cin >> a >> b; //Вписываем координаты пункта назначения

}

cout << "Минимальное количество шагов :" << BFS(src, dest);

}







//// исходные координаты
//Node src = { 0, 1 };

//// координаты пункта назначения
//Node dest = { 1, 1 };

//cout << "Минимальное количество шагов :" << BFS(src, dest);

return 0;
}[/CPP]

должно получиться примерно такое, но у меня оно не правильно работает
Можете помочь с Node, что бы оно правильно записывалось