ОЛІМПІАДНА
ЗАДАЧА З ІНФОРМАТИКИ
Задача 1. (ХІІІ обласна олімпіада з інформатики – м. Житомир, 1999
р.)
Шаховий кінь. У файлi CHESS.DAT задано через пропуск координати стартової А (наприклад, А5) та кiнцевої В (наприклад, С7) клiтин маршруту коня. Вивести у перший рядок
файлу CHESS.SOL мiнiмальну кiлькiсть ходiв N для переходу з клiтини А на клiтину В. Наступнi N рядкiв повиннi мiстити один з можливих
маршрутiв по мiнiмальному маршруту з клiтини А у клiтину В. Програма повинна мати iм'я CHESS.*
Примiтка: Клiтини шахової дошки нумеруються по
горизонталi великими лiтерами латинського
алфавiту: A,B,C,D,E,F,G,H, а по вертикалi цифрами 1–8.
Приклад вхiдних та вихiдних даних:
CHESS.DAT
CHESS.SOL
A5 C7 4
B3
D4
B5
C7
Розв’язання: Дана задача допоможе нам познайомитись
з одним цікавим методом програмування, який відноситься до методів динамічного
програмування.
![]()
Рис. 1
|
Для початку
розглянемо довільне положення шахового коня на шаховій дошці. Припустимо, що
кінь знаходиться у клітинці Е6. На рисунку точками відмічено клітини, у які кінь може
піти при черговому ході. Таких клітин може бути від двох (у випадку, коли кінь
знаходиться у кутку дошки) до восьми (як у наведеному прикладі). Ідея
розв’язання полягає у відшуканні найкоротшого шляху від точки старту (Xstart, YStart) до точки фінішу (Xfine, YFine), тобто задача зводиться до відшукання
найкоротшого шляху виходу з лабіринту з заданим положенням коня і точкою виходу
з лабіринту (точка фінішу). Відомо багато способів відшукання такого шляху. Ми
ж будемо одночасно працювати з двома шаховими дошками: одну використаємо для
підрахунку кількості кроків до виходу, а іншу – для позначення номерів клітин,
з яких ми потрапляємо в чергову клітину.
Обидва масиви
спочатку заповнюємо нулями. Потім помічаємо клітину, у якій знаходиться кінь,
як пройдену – заносимо в неї 1, причому одночасно на обох дошках.
На кожному з
наступних кроків, доки не досягли клітини фінішу робимо так:
![]()
Рис. 2.
|
n переглядаємо всі клітини шахової дошки
і, якщо в них міститься номер ходу, то відшукуємо всі клітини, у які може піти
кінь, і заносимо в них значення номера ходу, який на 1 більше розглядуваного, а
на іншій дошці вказуємо координати клітини, з якої ми в неї прийшли;
n координати клітини обраховуємо за
формулою: k = X·10+Y;
n якщо досягли потрібної клітини, то
встановлюємо прапорець виходу з подальшого перегляду клітин дошки, у противному
випадку збільшуємо номер ходу на одиницю і повторюємо все спочатку.
Так, для
наведеного в умові прикладу значення масивів для клітин обох дощок будуть мати
такий вигляд, як зображено на рис. 2, 3. Стартову і кінцеву клітину маршруту
виділено більш товстими лініями.
Якщо досягли
потрібної клітини, то по другій дошці відшукуємо номери клітин, починаючи з
кінцевої, маршруту до стартової клітини, доки значення клітини не стане рівним
1 – це означає, що ми досягли стартової клітини. На кожному кроці координати
наступної клітини дошки визначаються за формулами: x = k div 10, y = k mod 10, де k – число, занесене у відповідну клітину
дошки. Власне кажучи, це є використання вказівників, але без їх прямого опису.
Отримані координати перетворюємо у назви клітин шахової дошки і у зворотному
порядку виводимо на екран.
Описаний алгоритм
розв’язання реалізовано у приведеній нижче програмі. Звертаємо увагу на
необхідність акуратного оформлення перевірки можливості чергового ходу коня
(процедура hod). Все інше
зрозуміло з тексту програми.
program chess;
const inname
= 'chess.dat';
outname = 'chess.sol';
var area, point : array[1..8,1..8] of byte;
namex : array[1..8] of
char;
i, j, XStart, YStart,
XFine, YFine, X, Y, step : byte;
f : text;
kod : integer;
c : char; st, st1 :
string;
flag : boolean;
procedure hod(x, y, step : byte);
begin
if (x - 2 > 0) and (y
- 1 > 0) and (area[x-2,y-1] = 0) then
begin
area[x-2,y-1] := step + 1;
point[x-2,y-1] := 10*x + y;
end;
if (x-2 > 0) and (y+1
< 9) and (area[x-2,y+1] = 0) then
begin
area[x-2,y+1] := step + 1;
point[x-2,y+1] := 10*x + y;
end;
if (x+2 < 9) and (y-1
> 0) and (area[x+2,y-1] = 0) then
begin
area[x+2,y-1] := step + 1;
point[x+2,y-1] := 10*x + y;
end;
if (x+2 < 9) and (y+1
< 9) and (area[x+2,y+1] = 0) then
begin
area[x+2,y+1] := step + 1;
point[x+2,y+1] := 10*x + y;
end;
if (x-1 > 0) and (y-2
> 0) and (area[x-1,y-2] = 0) then
begin
area[x-1,y-2] := step + 1;
point[x-1,y-2] := 10*x + y;
end;
if (x-1 > 0) and (y+2
< 9) and (area[x-1,y+2] = 0) then
begin
area[x-1,y+2] := step + 1;
point[x-1,y+2] := 10*x + y;
end;
if (x+1 < 9) and (y-2
> 0) and (area[x+1,y-2] = 0) then
begin
area[x+1,y-2] := step + 1;
point[x+1,y-2] := 10*x + y;
end;
if (x+1 < 9) and (y+2
< 9) and (area[x+1,y+2] = 0) then
begin
area[x+1,y+2] := step + 1;
point[x+1,y+2] := 10*x + y;
end;
end;
procedure back_and_print;
begin
assign(f, outname);
rewrite(f);
st := '';
X := XFine; Y := YFine;
repeat
st1 := namex[X]; st := st + st1;
str(Y,st1); St := st + st1;
XFine := point[x,y] div 10;
YFine := point[x,y] mod 10;
x := xfine; Y := Yfine;
until point[x, y] = 1;
writeln(f, step);
writeln(step);
kod := length(st) - 1;
while kod >= 1 do
begin
writeln(f,copy(st,kod,2));
writeln(copy(st,kod,2));
dec(kod,2);
end;
close(f);
end;
begin
fillchar(area,
sizeof(area), 0);
fillchar(point,
sizeof(point), 0);
namex[1]:='A';
for i:=2 to 8 do
namex[i] := succ(namex[i-1]);
assign(f, inname);
reset(f); readln(f,st); close(f);
c := st[1];
for i:=1 to 8 do if
c=namex[i] then XStart := i;
c := st[2];
val(c,YStart,kod);
c := st[4];
for i:=1 to 8 do if
c=namex[i] then XFine := i;
c := st[5]; val(c,
YFine, kod);
X := XStart; Y: =
YStart;
flag := false; step :=
1;
area[xStart, yStart] :=
step;
point[Xstart, yStart] :=
1;
while flag = false do
begin
for i := 1 to 8 do
for j := 1 to 8 do
if area[i,j] = step then hod(i, j, step);
if area[XFine,YFine] > 0
then flag := true
else inc(step);
end;
back_and_print;
end.
Немає коментарів:
Дописати коментар