на шахматной доске заданы 2 клетки соедините эти 2 клетки кратчайшим путем коня

[Ker_33rus]

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

Ребят хотя бы алгоритм, а то шахматы не мое

[Markiz]

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

Но это скорее-всего по StackOverflow вывалится. У такой задачи обязано быть красивое решение

[Stilet]

У такой задачи обязано быть красивое решение

Один мой знакомый рассудил так. Ход коня образует катеты прямоугольного треугольника, стало быть нужно просто рассчитать расстояние от точек как гипотенузу главного треугольника, в который вхотят маленькие треугольникики, являющиеся ходами коня. Таким образом получив их наименьшее кол-во получаем собственно сам путь.
Дальнейшие его рассуждения я не помню, но он задачу эту именно так решил. Преподаватель был в шоке и отослал решение на кафедру математики

[Ker_33rus]

#include <iostream>  
using namespace std;
int main()
{
	int desk[8][8] = {10}; // доска 8х8. пусть незанятые клетки будут равны 10
	int nkx, nky, kkx, kky, x, y, n;
	cout<<"Vvedite na4alnoe pologenie kon9I\n";
	cin>>nkx;
	cin>>nky;
	cout<<"Vvedite kone4noe pologenie kon9I\n";
	cin>>kkx;
	cin>>kky;
	x=nkx;
	y=nky;
	n=1;
	if (desk[x+3][y+1]==10)
	{
		desk[x+3][y+1]=n;
	}
	if (desk[x+3][y-1]==10)
	{
		desk[x+3][y-1]=n;
	}
	if (desk[x-3][y+1]==10)
	{
		desk[x-3][y+1]=n;
	}
	if (desk[x-3][y-1]==10)
	{
		desk[x-3][y-1]=n;
	}
	if (desk[x+1][y-3]==10)
	{
		desk[x+1][y-3]=n;
	}
	if (desk[x+1][y+3]==10)
	{
		desk[x+1][y+3]=n;
	}
	if (desk[x-1][y-3]==10
	{
		desk[x-1][y-3]=n;
	}
	if (desk[x-1][y+3]==10)
	{
		desk[x-1][y+3]=n;
	}
for (int i=0; i<8; i++)
{
	for(int j=0; j<8; j++)
	{
		if (desk[i][j]==1)
		{
			
		}
}

ребят помогите с кодом застопорился чего дальше в последнем иф писать

[Ozerich]

Если задача состоит найти за какое наименьшее кол-во ходов конь дойдет из точки А в точку Б, то используй поиск в ширину.

[ds.Dante]

Самый оптимальный по скорости вариант: хранить в файле решения для 504 комбинаций (с учётом поворотов и отражений доски) начального и конечного пункта.

UPD: если брать не положение пунктов относительно краёв доски, а положение одного относительно другого, остаётся всего лишь 35 вариантов. По-моему, это даже проще рекурсивного алгоритма.