четвер, 10 листопада 2016 р.

ХІІІ обласна олімпіада з інформатики – м. Житомир, 1999 р

ОЛІМПІАДНА   ЗАДАЧА З ІНФОРМАТИКИ
Задача 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.
8
26
36
17
27
46
47
57
67

7
36
15
16
26
36
46
56
0

6
24
34
15
27
35
45
55
65

5
1
13
23
24
34
44
54
0

4
22
36
15
23
35
43
53
63

3
34
15
12
22
34
42
52
0

2
24
34
11
23
31
41
53
61

1
23
13
23
22
32
42
52
0


1
2
3
4
5
6
7
8






         Рис. 3



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.

Немає коментарів:

Дописати коментар