2 коня

#include <iostream>
using namespace std;

const int inf = 100;

struct kletka
{
  public:
  int x, y;
  void new_kletka(int x, int y)
  {
    this->x = x;
    this->y = y;
  }
  void print_kletka()
  {
    cout << x+1 << " " << y+1 << " ";
  }
};

class vershina
{
 public:
 int cost;
 kletka* data;
 vershina* prev;
 vershina* next;

 vershina(kletka* data, int cost, vershina* prev = nullptr)
 {
   this->data = data;
   this->cost = cost;
   this->prev = prev;
   this->next = nullptr;
 }
 void print_v()
 {
   cout << data->x + 1 << " " << data->y + 1 << endl;
 }
};

class queue
{
  public:
    queue()
    {
        size = 0;
        head = nullptr;
        tail = nullptr;
    }

    vershina* head;
    vershina* tail;
    int size;

    void push_back(kletka* data, int cost = 0, vershina* prev = nullptr)
    {
        vershina* yzel = new vershina(data, cost, prev);
        if (head == nullptr)
        {
            head = yzel;
            tail = yzel;
        }
        else
        {
            tail->next = yzel;
            tail = yzel;
        }
        size++;
    }

    vershina* pop_front()
    {
        if (size == 0)
            return 0;

        vershina* result = head;
        head = head->next;
        size--;
        return result;
    }

    int GetSize()
    {
        return size;
    }
};

class Graph
{
public:
    queue red_Q, green_Q;
    kletka **main_board;
    int dlina = 0, *dx, *dy;
    bool **board_red, **board_green;
    kletka start_red, start_green;
    Graph(int x1, int y1, int x2, int y2)
    {
       start_red.new_kletka(x1, y1);
       start_green.new_kletka(x2, y2);

      board_red = new bool*[8]{0};
      board_green = new bool*[8]{0};
      main_board = new kletka*[8];

      for (int i = 0; i < 8; i++)
        {
          board_red[i] = new bool[8]{0};
          board_green[i] = new bool[8]{0};
          main_board[i] = new kletka[8];
        }

      for (int i= 0; i < 8; i++)
       for (int j = 0; j < 8; j++)
        main_board[i][j].new_kletka(i, j);

      board_red[x1][y1] = 1;
      board_green[x2][y2] = 1;

      dx = new int[8]{2, 2, 1, 1, -1, -1, -2, -2};
      dy = new int[8]{1, -1, 2, -2, 2, -2, 1, -1};

      if (x1 == x2 && y1 == y2)
       cout << 0;
      else
       poisk(start_red, start_green);
    }
    void poisk(kletka start_red, kletka start_green);
    bool check_access(kletka* a, kletka* b);
    void all_way(vershina* red, vershina* green, int dlina);
    void variant(vershina* a, queue* Q, bool **board);
    void get_arr();
};

void Graph::variant(vershina* a, queue* Q, bool **board)
{
  int u = 0, v = 0;

  for (int i = 0; i < 8; i++)
   {
     u = a->data->x + dx[i];
     v = a->data->y + dy[i];

     if (u >= 0 && u < 8 && v >= 0 && v < 8 && !board[u][v])
      {
        Q->push_back(&main_board[u][v], a->cost+1, a);
        board[u][v] = 1;
      }
   }
}

bool Graph::check_access(kletka* a, kletka* b)
{
 bool x = false;
 for (int i = 0; i < 8; i++)
  if (a->x == b->x + dx[i] && a->y == b->y + dy[i] )
     x = true;

 return x;
}

void Graph::poisk(kletka start_red, kletka start_green)
{
  vershina* current = new vershina(&start_red, 0);
  variant(current, &red_Q, board_red);

  green_Q.push_back(&start_green);

  while (red_Q.GetSize() != 0 && green_Q.GetSize() != 0)
  {
    int red_size = red_Q.GetSize();
    int green_size = green_Q.GetSize();

    vershina** red = new vershina*[red_size];
    vershina** green = new vershina*[green_size];

    for (int i = 0; i < red_size; i++)
       red[i] = red_Q.pop_front();

    for (int i = 0; i < green_size; i++)
       green[i] = green_Q.pop_front();

   for (int i = 0; i < red_size; i++)
     for (int j = 0; j < green_size; j++)
      if (check_access(red[i]->data, green[j]->data) == true)
        {
                  all_way(red[i], green[j], red[i]->cost);
                  return;
        }

      for (int i = 0; i < red_size; i++)
                variant(red[i], &red_Q, board_red);

      for (int i = 0; i < green_size; i++)
                variant(green[i], &green_Q, board_green);
 }
 cout << -1;
 return;
}

void Graph::all_way(vershina* red, vershina* green, int dlina)
{
       kletka* r = new kletka[dlina];
        kletka* g = new kletka[dlina];

        vershina* current_red = red;
        vershina* current_green = green;
        int i = 0;

        while (current_red->data->x != start_red.x or current_red->data->y !=start_red.y)
        {
            r[i] = *current_red->data;
            g[i+1] = *current_green->data;
            current_red = current_red->prev;
            current_green = current_green->prev;
            i++;
        }
        g[0] = r[0];

    cout << red->cost << endl;

        for (int i = dlina-1; i >= 0; i--)
        {
            r[i].print_kletka();
            g[i].print_kletka();
        }
}

int main()
{
    int x, y, x2, y2;
    cin >> x >> y >> x2 >> y2;
    Graph object(x-1, y-1, x2-1, y2-1);
}