какая фигура раньше доберется до заданной точки на шахматной доске

[Вася Маклауд]

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

[Serge_Bliznykov]

любопытная задачка..

язык программирования какой?
Наработки есть?
Если несколько фигур могут добраться за одинаковое число ходов - то в ответе что должно быть? (все варианты? Один любой? Один вариант - первый подходящий по порядку перечисления фигур?)

[rrrFer]

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

Если же надо вывести 1 любое решение - то полный перебор не нужен. Сначала проверяем достигает ли конь нужную клетку за 1 ход. Если достигает то решение - "конь, 1 ход", иначе решение "ферзь, Х ход(ов)", X<=2. Х = 1 если ферзь достигает нужную точку за 1 ход(проверить диагонали и горизонтали, я думаю, не сложно), иначе - Х = 2.

[rrrFer]

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

D = max ( | StartX - FinishX | , | StartY - FinishY | )

не проверял. Тут "| |" - это модуль

[Serge_Bliznykov]

rrrFer, кстати, коллега, я мыслил полностью так же!

Поэтому и задал вопросы TC - какой вариант нужно/можно выводить...
Если один любой, тогда задача сильно упрощается (чистая арифметика), если же все - надо будет для коня перебирать все варианты и искать самый короткий...

[Вася Маклауд]

Serge_Bliznykov и rrrFer,отвечаю на ваши вопросы)
1.Язык паскаль!
2.если одинаковое количество ходов то выводить старшую по цене(король,ферзь,ладья,слон,конь).
3.препод нашла задачу эту и там как оказлось объявляются клетки в которые нельзя фигуре попадать)
4.Я как понял вы предлагаете решать графами,но вот с ними я пока незнаком(так что если моно расписать примерно)
5,пытался действовать методом перебора(т.е ставил циклы и проверял ходы если фигура попадала в ту клетку в которую якобы нельзя тогда смарел другой ход)но к особо радужным результатам это не привело,к тому же мой препод эт бабушка без пед.образования так что ее объяснения мне не подвластны. Ибо она объясняет одно я прихожу домой и нахожу другое решение.

[Вася Маклауд]

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

[rrrFer]

Вася Маклауд
у нас тоже нет пед.образования(думаю ни у кого?)
Не понятно что значит "клетка в которую нельзя фигуре попадать". Судя по дальнейшему описанию это уже пройденная клетка(я правильно понял?)
Графы тут никто не предлагал.
Ладью и слона вообще выкиньте из рассмотрения если:

выводить старшую по цене(король,ферзь,ладья,слон,конь).

ЗЫ: на паскале не пишу, помочь не смогу(ИМХО, тут никто и не хочет помогать пока вы сами не приложите усилий{мы не увидим вашего кода}?)

[rrrFer]

клетки в которые нельзя попадать даются в условии,также в условии даются координаты начальной и конечной точки.

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

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