INFOMAN брой 7
{ This is the input data:
D4 A3 A8 H1 H8
КАМЕЛОТ
-------
Задачата е от втория ден на международната олимпиада
по информатика в Португалия през 1998 година.
Дадена е стандартна шахматна дъска 8 x 8. Всяко поле от дъската може да
побере неограничен брой фигури. Върху дъската са разположени няколко коня и
един цар, който могат да се придвижват съгласно шахматните правила - коня в
осем полета на буквата "Г",а царя - в осемте съседни полета. Царя има право
да "язди" конете. Когато кон и цар се намират на едно и също поле, цярат мо-
же да се качи на коня и те да се движат заедно по правилата за движение на
коня.При дадени позиции на конете и на царя да се намери минималния брой хо-
дове за които всички фигури могат да се съберат в едно и също поле. Това по-
ле може да е произволно поле от дъската. Данните са в следния вид: координа-
ти на царя, координати на първия кон, на втория кон и т.н. Координатите се
състоят от двойка главна латинска буква и цифра (както при шахмата).За един
ход се брои едно преместване на фигура. Ако царя язди кон, придвижването на
царя и коня едновременно се счита за един ход.
РЕШЕНИЕ: Задачата ще решим като за всяко възможно поле от дъската изчис-
лим минималния брой ходове, за който всички фигури могат да се съберат в то-
ва поле и изберем оптималния вариант. Изчисляването на минималния брой ходо-
ве за събиране на всички фигури в дадено поле става така: Нека D[x,y,dx,dy]
е минималното разстояние с кон от поле (x,y) до поле (dx,dy) и W[x,y,dx,dy]
е минималното разстояние с цар от поле (x,y) до поле (dx,dy) и полето,в кое-
то трябва да съберем всички фигури е (DestX,DestY).Нека да изберем един кон
K, на който да качим царя и едно поле от дъската (Xk,Yk), в което царят се
качва на коня. Тогава броят ходове е сумата от ходовете, необходими на всич-
ки коне без K-тия, да дойдат до крайното поле (DestX,DestY) + броя ходове,
необходими конят да дойде до полето (Xk,Yk) + броя ходове, за които цяря ид-
ва до поле (Xk,Yk) + броя ходове, за които царя и коня достигат до крайното
поле, който е D[Xk,Yk,DestX,DestY]. За Xk, Yk и K се взимат всичи допустими
стойности. С други думи минималния брой ходове за събиране на всички фигури
в едно поле се изчислява като сбор от броя ходове за достигане на това поле
от всички коне без един плюс броя ходове необходим на този останал кон и ца-
ря да достигнат крайното поле. Броя ходове на царя и останалия кон се изчис-
лява като се пробва този кон да се придвижи до всяко поле, царят да се прид-
вижи до това поле и да се качи на коня и заедно конят и царят да се придви-
жат до крайното поле. Ясно е, че царя няма нужда да язди повече от един кон
и затова той трябва винаги да се качи на един от конете (ако той върви само
пеш, то той пак се качва на някой кон, но в крайното поле). Нека P[1..N] са
позициите на конете а P[0] е позицията на царя.Би могъл да се използва след-
ният алгоритъм:
Min:=безкрайност
for DestX = 1 to 8
for DestY = 1 to 8
for K = 1 to N
for Xk = 1 to 8
for Yk = 1 to 8
S:= Sum - D[ P[K], DestX,DestY ]
+ D[ P[K], Xk,Yk ]
+ D[ Xk,Yk, DestX,DestY ]
+ W[ P[0], Xk,Yk )
if S < Min then Min:= S
Отпечатай (Min)
Тук със Sum означаваме сумата D[ P[i], DestX,DestY ] за i=1..N. Алгоритъмът
реализира описаната по-горе идея - за качването на царя на всеки кон на вся-
ко поле от съската като проверява броя ходове за събиране на всички фигури
във всяко поле от дъската. Този алгоритъм проверява вискчи възможности и за-
това винаги намира оптималния резултат. Той може да се оптимизира, както е
направено в програмата. Намирането на разстоянията с кон между всеки две по-
зиции на дъската - матрицата D[...] се прави по метода търсене в ширина. От
всяко поле се обходжа цялата дъска в ширина по ходове на коня и се запазват
минималните разстояния с матрицата D.
}
CONST InFileName = 'CAMELOT.PAS';
OutFileName = '';
MaxKnights = 128;
MaxN = 8; {ширина на дъската в брой полета}
TYPE Pozition = record x,y:byte; end;
VAR P: array[0..MaxKnights] of Pozition; {позиции на царя и конете}
D: array[1..MaxN,1..MaxN,1..MaxN,1..MaxN] of byte; {конски разстояния}
Count: integer; {брой коне}
Procedure ReadData; { Прочита входните данни - P[0], Count, P[1..Count] }
Var F: Text;
ch1,ch2,ch: char;
Begin
Assign(F,InFileName); Reset(F); ReadLn(F);
Count:=-1;
repeat
Read(F,ch1,ch2,ch);
Inc(Count);
P[Count].x:= ord(ch1)-ord('A')+1;
P[Count].y:= ord(ch2)-ord('1')+1;
until ch <> ' ';
Close(F);
End;
Procedure FindKnightsDistances;
{ Намира конските разстояния между всеки две полета - матрица D[] }
Var Visited: array[1..MaxN,1..MaxN] of boolean;
Procedure BFS(BegX,BegY:integer); { Обхожда в ширина от поле (BegX,BegY) }
Var ss: array[1..MaxN*MaxN] of record x,y,dist:integer; end;
sp,poz: integer;
Procedure add(x,y,dist:integer);
Begin { Добавя в опашката полето (x,y) ако то вече не е било посетено }
if (x<1) or (x>MaxN) or (y<1) or (y>MaxN) or Visited[x,y] then Exit;
Visited[x,y]:=true;
inc(sp); ss[sp].x:=x; ss[sp].y:=y; ss[sp].dist:=dist;
D[BegX,BegY,x,y]:=dist;
End;
Var x,y,dist: integer;
Begin
sp:=0; add(BegX,BegY,0); poz:=1;
repeat
x:=ss[poz].x; y:=ss[poz].y; dist:=ss[poz].dist + 1;
add(x+1,y+2,dist);
add(x+1,y-2,dist);
add(x+2,y+1,dist);
add(x+2,y-1,dist);
add(x-1,y+2,dist);
add(x-1,y-2,dist);
add(x-2,y+1,dist);
add(x-2,y-1,dist);
inc(poz);
until poz > sp;
End;
Var x,y: integer;
Begin
for x:= 1 to MaxN do
for y:= 1 to MaxN do
begin
FillChar(Visited,SizeOf(Visited),false);
BFS(x,y);
end;
End;
Procedure Print(Result:integer); { Отпечатва Result в изходния файл }
Var OutF: Text;
Begin
Assign(OutF,OutFileName); Rewrite(OutF);
Writeln(OutF,Result);
Close(OutF);
End;
Function Minimal: integer;
{ Намира минималния брой ходове за събирането на всички фигури в едно поле }
Var i, DestX, DestY, Sum, BestSum: integer;
Procedure CalculateMinimalToDest;
{ Намира мин.брой ходове за събиране на всички фигури в поле (DestX,DestY) }
Function WalkDist(x1,y1,x2,y2:integer): integer;
Function Max(a,b:integer): integer;
Begin if a>b then Max:=a else Max:=b; End;
Begin WalkDist:=max(abs(x2-x1),abs(y2-y1)); End;
Var Knight, MountX, MountY, TotalSum: integer;
Begin
for Knight:= 1 to Count do
for MountX:= 1 to MaxN do
for MountY:= 1 to MaxN do
begin
TotalSum:= Sum - D[ P[Knight].x,P[Knight].y, DestX,DestY ]
+ D[ P[Knight].x,P[Knight].y, MountX,MountY ]
+ D[ MountX,MountY, DestX,DestY ]
+ WalkDist( P[0].x,P[0].y, MountX,MountY );
if TotalSum < BestSum then
BestSum:=TotalSum;
end;
End;
Begin
BestSum:=MaxInt;
for DestX:= 1 to MaxN do
for DestY:= 1 to MaxN do
begin
Sum:=0;
for i:= 1 to Count do
Sum:= Sum + D[P[i].x,P[i].y, DestX,DestY];
if Sum < BestSum then CalculateMinimalToDest;
end;
Minimal:=BestSum;
End;
BEGIN
ReadData;
FindKnightsDistances;
Print(Minimal);
END.