Шахматная доска.Перемещение

[yzen]

Поле шахматной доски определяется парой натуральных чисел, каждое из которых не превосходит восьми: первое число — номер вертикали (при счете слева направо), второе — номер горизонтали (при счете снизу вверх). Даны натуральные числа k, l, m, n, каждое из которых не превосходит восьми. Требуется:
Выяснить, можно ли с поля (k, l) одним ходом конь попасть на поле (m, n). Если нет, то выяснить, как это можно сделать за два хода (указать поле, на которое приводит первый ход).
Предполагается, что указанные поля имеют один и тот же цвет.

[waleri]

А разве конь может перейдти на поле с тем же цветом? Т.е. если цвета одинаковые одним ходом точно не получится.

[yzen]

На такого же цвета перейти не может.
Просто было в условие.
так в голове наброски есть
а толком не чего не могу написать

[Serge_Bliznykov]

А разве конь может перейдти на поле с тем же цветом? Т.е. если цвета одинаковые одним ходом точно не получится.

Если нет, то выяснить, как это можно сделать за два хода (указать поле, на которое приводит первый ход).

за два хода коня как раз цвет начального поля совпадёт с цветом конечного (второго) поля.

[yzen]

Лучше бы помог
мне это не особо много дало

[waleri]

Сообщение от Serge_Bliznykov

за два хода коня как раз цвет начального поля совпадёт с цветом конечного (второго) поля.

Я в курсе. Меня просто удивила формулировка условия.

[Serge_Bliznykov]

Сообщение от waleri

в курсе. Меня просто удивила формулировка условия.

вы про это?

Сообщение от yzen

Предполагается, что указанные поля имеют один и тот же цвет.

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


yzen, мыслей как решить задачу нет совсем-совсем?..
я не уверен, что предложу оптимальное решение, но, на крайний случай, могу вам предложить такой алгоритм:
1. Делаем перебор от 1 до 8 всех потенциально возможных ходов коня из исходной точки (пусть будут получаться точки с координатами iC, iR).
2, в цикле проверяем возможность из этой полученной точки (iC, iR) одним ходом достичь конечной точки (m, n) (это ещё проще:

if ((abs(iC-m)=2) and (abs(iR-n)=1)) or ((abs(iC-m)=1) and (abs(iR-n)=2)) 
then 
   // можно переместить коня из точки (iC, iR)  в точку (m, n)
   // вот тут и выдаём нужные координаты и устанавливаем флажок, что задача имеет решение!
else 
  // нет, нельзя - ничего не делаем (данный вариант нас не устраивает)

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

профит.

[waleri]

Сообщение от Serge_Bliznykov

вы про это?

Я про это:
"Выяснить, можно ли с поля (k, l) одним ходом конь попасть на поле (m, n). Предполагается, что указанные поля имеют один и тот же цвет."
Соотвественно а) я в курсе что нужны два хода б) зачем выяснять, когда понятно, что одного хода недостаточно... хотя наверно надо *доказать* что одним ходом конь всегда меняет цвет

[rrrFer]

на вот: (на коленке написал одну из унылых унылых реализаций обхода поля конем в ширину)

#include <vector>
#include <iostream>
#include <algorithm>
typedef std::pair<int, int> Ceil;

bool isEqualCeil(const Ceil a, const Ceil b) {
	return a.first == b.first && a.second == b.second;
}

bool check(const std::vector<Ceil> vec
				, const Ceil val) {
	return val.first > 0 && val.second > 0 && val.first < 9 && val.second < 9
					&& vec.end() == std::find_if(vec.begin(), vec.end(),
					[ = ](Ceil i)->bool{return isEqualCeil(i, val);});
}

int main() {
	std::vector<Ceil> ceils;
	Ceil finish = std::make_pair(1, 8),
					start = std::make_pair(3, 4);
	ceils.push_back(start);

	auto it = ceils.begin();
	while (ceils.end() != it) {
		if (isEqualCeil(*it, finish))
			break;
		const int x = (*it).first, y = (*it).second;
		if (check(ceils, std::make_pair(x + 1, y + 2)))
			ceils.push_back(std::make_pair(x + 1, y + 2));
		if (check(ceils, std::make_pair(x - 1, y + 2)))
			ceils.push_back(std::make_pair(x - 1, y + 2));
		if (check(ceils, std::make_pair(x + 1, y - 2)))
			ceils.push_back(std::make_pair(x + 1, y - 2));
		if (check(ceils, std::make_pair(x - 1, y - 2)))
			ceils.push_back(std::make_pair(x - 1, y - 2));

		if (check(ceils, std::make_pair(x + 2, y + 1)))
			ceils.push_back(std::make_pair(x + 2, y + 1));
		if (check(ceils, std::make_pair(x - 2, y + 1)))
			ceils.push_back(std::make_pair(x - 2, y + 1));
		if (check(ceils, std::make_pair(x + 2, y - 1)))
			ceils.push_back(std::make_pair(x + 2, y - 1));
		if (check(ceils, std::make_pair(x - 2, y - 1)))
			ceils.push_back(std::make_pair(x - 2, y - 1));
		++it;
	}

	std::for_each(ceils.begin(), ceils.end(), [](Ceil ceil) {
		std::cout << '(' << ceil.first << ',' << ceil.second << ')' << std::endl;
	});

	return 0;
}

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

struct Ceil { int x, y, depth; };

со структурой будет красивше, обещаю.
Чтобы вывести путь замени цикл хвостовой рекурсией, на возврате будет тебе путь.

[yzen]

Забыл указать//
надо на паскале