INFOMAN брой 6
{ This is the input data - Xsize; Ysize; Stars map
20
15
* * * ú ú ú * * * ú ú ú ú ú ú ú ú ú * ú
* ú ú * ú ú ú ú * ú ú ú ú ú * ú ú * ú ú
* ú ú ú ú ú ú ú * ú ú * ú ú * ú ú * ú ú
ú ú * * * ú ú * ú ú ú ú * * * ú ú * * *
ú ú ú ú * ú ú ú ú ú ú ú ú ú ú ú ú ú ú ú
* ú * ú ú ú ú * * ú ú * * * ú ú ú ú ú ú
* ú ú ú * ú ú ú * ú ú ú ú * ú ú ú * * *
ú ú ú * * ú ú ú ú ú ú ú * * * ú ú * ú ú
ú * ú ú ú ú ú * ú ú * ú ú * ú ú * * * ú
ú ú ú * * ú * * ú ú * * ú ú ú ú ú * ú ú
ú ú ú ú ú ú ú ú ú ú ú ú ú ú **ú ú ú ú ú
ú * * * ú ú * * * ú ú * ú ú ú ú ú ú * ú
* ú ú * ú ú * ú ú ú ú * ú ú * ú ú ú ú *
ú ú ú * ú ú * ú ú ú ú * * * ú ú ú ú ú *
ú ú ú ú ú ú ú * ú ú ú ú ú ú ú ú ú * * *
РАЗПОЗНАВАНЕ НА СЪЗВЕЗДИЯ
-------------------------
(Задачата е от 10-тата международна олимпиада по информатика - ден I)
Звездна карта представлява правоъгълна таблица. Във всяко поле или има
звезда (означава се с "*") или няма нищо (означава се с друг знак). Съзвез-
дие се нарича съвкупност от 1 или няколко съседни звезди. Две звезди са съ-
седни, ако са разположени отгоре, отдолу, отляво, отдясно или по диагонал
в съседни едно до дръго полета. Две съзвездия се наричат подобни, ако имат
еднакъв брой звезди и една и съща форма, независимо от ориентацията. Броят
на различните ориентации е 8 и те са: съзвездието, съзвездието, завъртяно
на 90ø, 180ø или 270ø, осева симетрия на съзвездието и осева симетрия съот-
ветно завъртяна на 90ø, 180ø или 270ø. Задачата е по дадена звездна карта
да се отпечата същата звездна карта, но еднаквите съзвездия да се означат
с еднакви букви от латинската азбука, а различните - с различни.Означаване-
то става като се замести знака "*" със съответната буква. Максималния раз-
мер на звездната карта е 100 x 100, максималния брой съзвездия - 500, макс.
брой звезди в съзвездие - 160 и макс. брой различни съзвездия на картата -
26 (за да могат да се означават с 'a'..'z').
РЕШЕНИЕ: Решението на задачата можем да разделим на няколко етапа:
(1) Прочитане на входните данни (виж ReadData).
(2) Намиране на всички съзвездия и съхраняване на формата и позицията им
в масив (виж FindAllSazv).
(3) Разпознаване на всички двойки подобни съзвездия и означаване на всич-
ки подобни едно на друго съзвездия с еднаква буква (виж FindSimilars).
(4) Създаване на търсената карта и отпечатване (виж PrintStarMap).
Първо прочитаме входните данни в масива K[], който ще ни е звездната карта.
След това трябва да намерим всички съзвездия на тази карта.За целта трябва
да помислим как ще ги съхраняваме. Структурата данни, която избираме, не е
случайна и тя е такава, че проверката дали две съзвездия са подобни (което
е същината на задачата) да е максимално опростена. Представяме всяко съзве-
здие като списък от координатите на звездите му. Намирането на съзвездията
се извършва по метода на рекурсивното обхожане в дълбочина. Картата се ска-
нира и когато се срещне звезда, то е намерено ново съзвездие. От тази звез-
да се пуска обхождане в дълбочина и така се намира цялото съзвездие. Наме-
рените звезди се отбелязват като обработени,за да не се обхождат втори път.
Това се прави в FindAllSazv. Всяко съзвездие се нормализира - премества се
така, че минималната X координата и минималната Y координата на звезда от
него да е 0 и звездите се сортират в нарастващ ред спрямо координатите си.
На всяко съзвездие се намира ширината и дължината (максималната Y и X коор-
дината). Това се прави, за да се улесни проверката за еднаквост на съзвез-
дия. Две съзвездия са подобни, ако едното може да се завърти по някой от 8-
те ориентации, че след като се нормализира, то да има:
- еднакъв брой звезди с другото;
- еднаква ширина и дължина;
- еднакъв списък от координатите на звездите.
Именно по тези 3 критерия функцията Similar определя дали две съзвездия са
подобни. Функцията първо сравнява броя на звездите, после проверява разме-
рите на двете съзвездия и ако е възможно те да са подобни, завърта първото
в 8-те му ориентации и проверява дали то съвпада с другото, като за целта
предварително го нормализира,за да може да го сравнява. 8-те ориентации се
получават само с помощта на комбинации от две процедури - за завъртане на
90ø и за централна симетрия.
Означаването на всички подобни съзвездия с еднаква буква се извършва така:
Взема се първото съзвездие и се означава с 'a'. Всяко подобно на него съз-
вездие се означава със същата буква.Взема се следващото по номер съзвездие,
което обаче все още няма буква. Съпоставя му се следващата буква от азбука-
та и отново се маркират всички подобни на него съзвездия (те имат задължи-
телно по-големи номера) с тази буква. Това се повтаря докато всички съзвез-
дия получат буква. Отпечатването на резултатите не е трудно. Понеже всяко
съзвездие си има буква, трябва само звездите, които са от него на звездна-
та карта да се означат с тази буква. Това отново става с търсене в дълбочи-
на.Понеже за всяко съзвездие предварително запазваме координатите на първа-
та му звезда, пускаме от това поле рекурсивно запълване със съпоставената
му буква. Така получаваме търсената звездна карта.
}
CONST InFileName = 'starry.pas';
OutFileName = '';
MaxSize = 100;
MaxSazvezdia= 500;
MaxStars = 160;
aStar = '*';
aPoseten = 'û';
vUnexplored = ' ';
TYPE TPoint = record x,y:shortint; end;
TCoords = array[1..MaxStars] of TPoint;
TSazv = record
StarsCount: integer;
MaxX,MaxY: integer;
Stars: TCoords;
Value: char; {Similar 'Sazv' has equal 'value'}
Xcoord,Ycoord: byte;
end;
VAR K: array[1..MaxSize,1..MaxSize] of char;
S: array[1..MaxSazvezdia] of ^TSazv;
SizeX,SizeY: integer;
SazvCount: integer;
Procedure ReadData;
{ Read the input data - SizeX; SizeY; Star Map (SizeX x SizeY) }
Var F: Text;
x,y:integer;
ch: char;
Begin
Assign(F,InFileName); Reset(F); ReadLn(F);
ReadLn(F,SizeX); ReadLn(F,SizeY);
for y:= 1 to SizeY do
begin
for x:= 1 to SizeX do
Read(F,K[X,Y],ch);
Read(F,ch); {ReadLn(F)}
end;
Close(F);
End;
Procedure MoveTo00(var S:TSazv);
{ Move the given sazvezdie to position (0,0) and sort its stars }
Procedure QuickSort(var A: Tcoords; Lo,Hi: Integer);
Procedure QSort(l,r: Integer);
Var i,j: integer;
x,tmp: TPoint;
Begin
i:= l; j:= r; x:= a[(l+r) div 2];
repeat
while (a[i].x < x.x) or ((a[i].x = x.x)and(a[i].y < x.y)) do
i := i + 1;
while (a[j].x > x.x) or ((a[j].x = x.x)and(a[j].y > x.y)) do
j := j - 1;
if i <= j then
begin
tmp:= a[i]; a[i]:= a[j]; a[j]:= tmp;
i:= i + 1; j:= j - 1;
end;
until i > j;
if l < j then QSort(l, j);
if i < r then QSort(i, r);
end;
Begin
QSort(Lo,Hi);
End;
Var i,MinX,MinY: integer;
Begin
MinX:=MaxInt; MinY:=MaxInt;
with S do
for i:= 1 to StarsCount do
with Stars[i] do
begin
if x < MinX then MinX:=x;
if y < MinY then MinY:=y;
end;
with S do
for i:= 1 to StarsCount do
with Stars[i] do
begin
x:= x - MinX;
y:= y - MinY;
end;
QuickSort(S.Stars,1,S.StarsCount);
End;
Procedure FindSazvSizes(var S:TSazv);
{ Calculate the MaxX and MaxY coordinate of the given sazvezdie }
Var i: integer;
Begin
S.MaxX:=-MaxInt; S.MaxY:=-MaxInt;
with S do
for i:= 1 to StarsCount do
with Stars[i] do
begin
if x > MaxX then MaxX:=x;
if y > MaxY then MaxY:=y;
end;
End;
Procedure FindAllSazv;
{ Find all sazvedia from the star map. Every star is part of some sazvezdie }
Procedure DFS(x,y:byte);
Begin
if (x < 1) or (x > SizeX) or (y > SizeY) or (y < 1) or
(K[x,y] <> aStar) then Exit;
K[x,y]:=aPoseten;
with S[SazvCount]^ do
begin Inc(StarsCount); Stars[StarsCount].x:=x; Stars[StarsCount].y:=y; end;
DFS(x+1,y); DFS(x-1,y); DFS(x,y+1); DFS(x,y-1);
DFS(x-1,y-1); DFS(x+1,y-1); DFS(x-1,y+1); DFS(x+1,y+1);
End;
Var x,y: integer;
Begin
for Y:= 1 to SizeY do
for X:= 1 to SizeX do
if K[x,y] = aStar then
begin
Inc(SazvCount);
New(s[SazvCount]);
s[SazvCount]^.Xcoord:=x;
s[SazvCount]^.Ycoord:=y;
s[SazvCount]^.StarsCount:=0;
s[SazvCount]^.Value:=vUnexplored;
DFS(x,y); {Find the stars in current sazvezdie}
end;
for x:= 1 to SazvCount do
MoveTo00(s[x]^);
for x:= 1 to SazvCount do
FindSazvSizes(s[x]^);
End;
Function Similar(a:TSazv; var b:TSazv): boolean;
{ Return if "a" and "b" are similar }
Procedure CentrSimetria;
Var i: integer;
Begin
with a do
for i:= 1 to StarsCount do
Stars[i].x:= MaxX - Stars[i].x;
End;
Function Equal: boolean; { Return true if a and b are completely equal }
Var i: integer;
Begin
Equal:=false;
MoveTo00(a);
for i:= 1 to a.StarsCount do
if (a.Stars[i].x <> b.Stars[i].x)
or (a.Stars[i].y <> b.Stars[i].y) then
Exit;
Equal:=true;
End;
Procedure Rotate90; { Rotate the sazvezdie "a" at 90ø }
Var i,OldY: integer;
Begin
with a do
for i:= 1 to StarsCount do
with Stars[i] do
begin
OldY:=y;
y:=x;
x:= maxY-OldY;
end;
i:=a.MaxX; a.MaxX:=a.MaxY; a.MaxY:=i;
End;
Begin
if NOT (((a.MaxX=b.MaxX)and(a.MaxY=b.MaxY)) OR
((a.MaxX=b.MaxY)and(a.MaxY=b.MaxX))) then
begin Similar:=false; Exit; end; {Different sizes --> not Similar}
Similar:=true; if Equal then exit; {Try 0ø equality}
Rotate90; if Equal then exit; {Try 90ø equality}
Rotate90; if Equal then exit; {Try 180ø equality}
Rotate90; if Equal then exit; {Try 270ø equality}
CentrSimetria; if Equal then exit; {Try symmetric 0ø equality}
Rotate90; if Equal then exit; {Try symmetric 90ø equality}
Rotate90; if Equal then exit; {Try symmetric 180ø equality}
Rotate90; if Equal then exit; {Try symmetric 270ø equality}
Similar:=false; {Not equal in all possible 8 oriantations --> not Similar}
End;
Procedure FindSimilars;
{ Find all similar sazvezdia. Similar sazvezdia obtain equal letters
in ".Value" field. Not similar obtain different letters than the other }
Var v: char;
i,j: integer;
Begin
v:=pred('a');
for i:= 1 to SazvCount do
if S[i]^.Value = vUnexplored then
begin
inc(v); S[i]^.Value:=v;
for j:= i+1 to SazvCount do
if Similar(S[i]^,S[j]^) then
S[j]^.value:=v;
end;
End;
Procedure PrintStarMap;
{ Create requested star map and print it in the output file }
Var v: char;
Procedure DFS(x,y:byte);
Begin { Fill current sazvezdie (x,y) with value v }
if (x < 1) or (x > SizeX) or (y > SizeY) or (y < 1) or
(K[x,y] <> aPoseten) then Exit;
K[x,y]:=v;
DFS(x+1,y); DFS(x-1,y); DFS(x,y+1); DFS(x,y-1);
DFS(x-1,y-1); DFS(x+1,y-1); DFS(x-1,y+1); DFS(x+1,y+1);
End;
Var OutF: Text;
i,x,y: integer;
Begin
{ Replace the stars on the map with their Value }
for i:= 1 to SazvCount do
with S[i]^ do
begin
v:=Value;
DFS(Xcoord,Ycoord);
end;
{ Print the map in the output file }
Assign(OutF,OutFileName); ReWrite(OutF);
for y:= 1 to SizeY do
begin
for x:= 1 to SizeX do
Write(OutF,K[x,y],' ');
WriteLn(OutF);
end;
WriteLn(OutF);
Close(OutF);
End;
BEGIN
ReadData;
FindAllSazv;
FindSimilars;
PrintStarMap;
END.