Соответствие Входа и Примера

[ViktorR]

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

Это как?
Помните:

... Рассмотрим неограниченную шахматную доску, на ...

Расстановка для второго случая:

 3! 0 0 0 0 0
 2! 0 0 0 0 0
 1! 0 h 0 0 0
 0! 0 h 0 0 0
-1! 0 0 0 0 0
-2! 0 0 0 0 0
----------------
   -1 0 2 3 4

Первый ход каждого коня:

 3! 0 0 0 0 0
 2! 0 0 0 1 0
 1! 0 h 0 0 0
 0! 0 h 0 0 0
-1! 0 0 0 1 0
-2! 0 0 0 0 0
----------------
   -1 0 2 3 4

Второй ход каждого коня:

 3! 0 0 0 0 0
 2! 0 0 0 1 0
 1! 0 h 2 0 0
 0! 0 h 2 0 0
-1! 0 0 0 1 0
-2! 0 0 0 0 0
----------------
   -1 0 2 3 4

Итого - 4 хода.
PS: Это как раз подтверждает (мой пост и следующий - Serge_Bliznykov), что кони должны встать на заданные поля, но какой конь может встать на какое поле - неважно: первый на первое поле или на второе и второй на любое другое свободное, и т.д.
PSS: На соседние поля (верхнее, нижнее, левое, правое) конь попадает за три хода.
На соседние диагональные - за два. Каждым шагом меняется цвет поля. Так как поле не ограничено, то нет проблем с угловыми полями. Если конь должен попасть на поле своего цвета - чётное число шагов, а на противоположного - нечётное.

[Programist_r]

Получилось как-то так...
Полазил по Гуглу, по изучал информацию и получилось сделать только для стандартной доски 8х8(решил начать с простого и дойти со временем до решения).Да и у меня в коде пропускается точка, если местоположение посещалось раньше.

И получается что надо решить проблему с доской и с местоположением которое посещалось раньше.
А как сделать это что-то не придумаю?
Если можете помочь, был бы очень благодарен вам)

#include "pch.h"
#include <iostream>
#include <map>
#include <queue>
#include <climits>
using namespace std;

#define N 8

//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;
}


struct Node
{
	// (x, y) представляет координаты шахматной доски
	//dist представляет минимальное расстояние от источника
	int x, y, dist;

	//конструктор
	Node(int x, int y, int dist = 0) : x(x), y(y), dist(dist) {}

	

	bool operator<(const Node& o) const
	{
		return x < o.x || (x == o.x && y < o.y);
	}
};

// Находим минимальное количество шагов для коня
int BFS(Node src, Node dest)
{
	// карта, чтобы проверить, посещалась ли ячейка матрицы раньше или нет
	map<Node, bool> 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;

		// если пункт назначения достигнут, вернуть расстояние
		if (x == dest.x && y == dest.y)
			return dist;

		// Пропустить, если местоположение посещалось раньше
		if (!visited.count(node))
		{
			// пометить текущий узел как посещенный
			visited[node] = true;

			// проверяем все 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 = { 1, 0 };

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

	cout<<BFS(src, dest);

	return 0;
}

[Programist_r]

Подскажите пожалуйста, очень нужно

[ViktorR]

Помочь не могу.
Может быть стоит подумать, нет ли некоторого правила заполнения полей доски числами, которые бы указывали, за сколько ходов конь может попасть на данное поле. У коня неслучайный набор ходов.
Картина положения ходов симметричная. Можно рассматривать только одну четверть. Остальные поля заполняются поворотом системы координат на 90 град.

[ViktorR]

Ещё немного.
Так думаю, что достаточно построить массив ходов (сколько ходов необходимо сделать, что бы попасть в нужную клетку) для круга, который охватывает позицию коня.
Когда конь перемещается на новую позицию, проверяем, попадает ли нужная клетка в круг его "интересов". Если да, то мы знаем сколько ходов дополнительно необходимо сделать, что бы конь оказался в нужной клетке.
Насколько это оптимально - не знаю.