Главная Вход в систему Регистрация
Задать вопрос Консультации Пользователи Форум
О системе Помощь
Задать вопрос экспертам
Консультация № 63901
23.11.2006, 18:15
0.00 руб.
0 5 1
Компьютеры Программирование
Здравствуйте, эксперты!!!
Помогите, пожалуйста, вот с такой задачкой.
На шахматной доске заданы координаты двух полей. Нужно определить наименьшее количество шагов, за которое конь может попасть с одного поля на другое.
Заранее спасибо, Денис

Обсуждение

давно
Вадим Исаев ака sir Henry
Мастер-Эксперт
425
4118
23.11.2006, 18:45
общий
Какой фигурой попасть? Или Вы там в Чапаева играете? :)
Об авторе:
Я только в одном глубоко убеждён - не надо иметь убеждений! :)
Неизвестный
23.11.2006, 19:00
общий
на шахматной доске (8 на 8) заданы 2 поля двумя своими координатами, нужно конем (фигура такая) попасть из одного поля в другое за наименьшее количество шагов
Неизвестный
23.11.2006, 22:53
общий
<b>sir henry</b>, там же написано сразу, что конем.<b>Гусев Денис</b>, я ж вам сегодня уже рассказывал, как решать подобную задачу. Сделайте по аналогии: заведите двумерный массив под поле доски. И перебирайте подобным образом. Только у вас внутри рекурсии будет не до 2, а до 8 вызовов самой себя.
давно
Вадим Исаев ака sir Henry
Мастер-Эксперт
425
4118
24.11.2006, 05:17
общий
Извиняюсь, глаз подвел. :)Вам нужно составить список возможных путей из одной заданной клетки в другую. Путь будет состоять из какого-то количества шагов. Вот где это количество меньше, тот тот путь и будет ответом.
Об авторе:
Я только в одном глубоко убеждён - не надо иметь убеждений! :)
Неизвестный
25.11.2006, 13:49
общий
это ответ
Здравствуйте, Гусев Денис!
Это вопрос скорее по алгоритму, а не по языку. Для большей теоретической подготовки рекомендую найти материалы по поиску в ширину (aka волновой алгоритм aka "заливка")

Приложение:
{$APPTYPE CONSOLE}uses SysUtils;const//Начальные координаты x0=1; y0=1;//Конечные координаты x=8; y=8;//Размер доски N=8;type TMove=record dx,dy:integer;end;//Возможные ходыconst MoveNum=8; Moves:array [1..MoveNum] of TMove= ((dx:2;dy:1),(dx:1;dy:2),(dx:-1;dy:2),(dx:-2;dy:1), (dx:-2;dy:-1),(dx:-1;dy:-2),(dx:1;dy:2),(dx:2;dy:-1));var Board:array [1..N,1..N] of integer; Step:integer; x1,y1,xn,yn:integer; i:integer;begin //Инициализация Step:=1; Board[x0][y0]:=Step; //Обход доски while Board[x][y]=0 do begin inc(Step); for y1:=1 to N do for x1:=1 to N do if Board[x1][y1]=Step-1 then for i:=1 to MoveNum do begin xn:=x1+Moves[i].dx; yn:=y1+Moves[i].dy; if (1<=xn) and (xn<=N) and (1<=yn) and (yn<=N) and (Board[xn][yn]=0) then Board[xn][yn]:=Step; end; end; //Результат WriteLn(Board[x][y]-1);end.
Форма ответа