|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitriy K. 2:5020/400 22 Jul 2002 15:59:08
To : Roman Zhelnov
Subject : Re: Обход доски шахматным конем
--------------------------------------------------------------------------------
Привет.
"Roman Zhelnov" <Roman.Zhelnov@p29.f25.n5053.z2.fidonet.org>
сообщил/сообщила в новостях следующее:
news:1027250589@p29.f25.n5053.z2.FIDOnet.ftn...
>
> [ы] Привет, как жизнь, All ?
>
> Интересует алгоритм обхода доски шахматным конем. Hа одну клетку можно
> вставать только один раз...
Hа - другую - тоже один раз, на третью - один раз и т.д. Рекурсия!
----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----
program MoveOfTheKnight;
const
DeskSize = 8; { Размер доски }
type
TCoords = 1..DeskSize; { возможные координаты доски }
TDesk = array[TCoords, TCoords] of Boolean; { Доски. Клетка либо пройдена,
либо нет }
TMove = record { ход }
X: TCoords;
Y: TCoords;
end;
const
NumOfKnightSteps = 8; { количество шагов конем из некоторого положения }
type
TKnightSteps = 1..NumOfKnightSteps;
const
KnightSteps: array[TKnightSteps] of record
DeltaX, DeltaY: Shortint
end = (
(DeltaX: -1; DeltaY: -2),
(DeltaX: 1; DeltaY: -2),
(DeltaX: 2; DeltaY: -1),
(DeltaX: 2; DeltaY: 1),
(DeltaX: -1; DeltaY: 2),
(DeltaX: 1; DeltaY: 2),
(DeltaX: -2; DeltaY: -1),
(DeltaX: -2; DeltaY: 1));
var
Desk: TDesk; { Доска }
MakedMoves: Integer; { Количество сделанных конем ходов }
const
MaxMoves = DeskSize * DeskSize; { Максимальное количество ходов }
var
Moves: array[1..MaxMoves] of TMove;
////////////////////////////////////////////////////////////////////////////
procedure PrintMoves; forward; { Вывод на экран результатов }
{ перемещение коня }
{ на входе: Pos - текущая позиция коня }
procedure Go(X, Y: TCoords);
var
i: TKnightSteps;
NewX, NewY: Shortint;
begin
{ Помечаем позицию, в которую пришли }
{ Writeln(MakedMoves); }
Desk[X, Y] := True;
Inc(MakedMoves);
Moves[MakedMoves].X := X;
Moves[MakedMoves].Y := Y;
if MakedMoves = MaxMoves then
PrintMoves { Hу вот, обшагали всю доску, результаты - на экран }
else
begin
{ Пытаемся найти подходящий ход }
for i := 1 to NumOfKnightSteps do
begin
{ Вычисление очередных координат }
NewX := X + KnightSteps[i].DeltaX;
if (NewX < 1) or (NewX > DeskSize) then Continue; { Выход за границы
доски - пропускаем }
NewY := Y + KnightSteps[i].DeltaY;
if (NewY < 1) or (NewY > DeskSize) then Continue; { Выход за границы
доски - пропускаем }
if not(Desk[NewX, NewY]) then Go(NewX, NewY); { Место не занято -
ходим туда }
end; { for... }
end; { if... }
{ Откат - помечаем позицию как непройденную }
Desk[X, Y] := False;
Dec(MakedMoves);
end;
procedure PrintMoves; { Вывод на экран результатов }
var
i: Integer;
begin
for i := 1 to MaxMoves do
with Moves[i] do
Write(X, ',', Y, '; ');
Writeln;
Writeln;
end;
begin
{ Обнулирование ;-) }
FillChar(Desk, SizeOf(Desk), 0);
MakedMoves := 0;
Go(1, 1);
WriteLn('Any Enter to continue...'); ReadLn;
end.
----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----8<----
Для случая 3x3 и необходимости обойти все поля, кроме центрального,
программка работает на ура.
Естественно, можно оптимизировать. Hапример, конь сделает только 64 хода,
так что можно избежать рекурсии, а сделать итерацию; посмотреть, как он
обходит и т.д.
Еще можно использовать факт симметрии доски и ходов - например, за один шаг
рекурсии делать не один шаг конем а все восемь в доступных направлениях.
>
> [ы] Пока, All, счастливого тебе коннекта ! ...
Та же фигня.
--
Отправлено через сервер Форумы@mail.ru - http://talk.mail.ru
--- ifmail v.2.15dev5
* Origin: Talk.Mail.Ru (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
