(*

Starry Night (IOI 1998)
Copyright (C) 2000 Sebastiano Vigna

This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.

This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA




Il problema non richiede conoscenze profonde per essere risolto, ma e` di
grande complicazione algoritmica. Gli off-by-one non si contano. Ci sono
dozzine di dettagli che e` molto difficile mettere a punto.

Inoltre, non e` banale trovare la strada giusta tra una soluzione
algoritmicamente elegante ed efficiente, ma di implementazione laboriosa, e
un'implementazione veloce da realizzare ma troppo lenta in esecuzione.

In una prima fase il file di input viene scandito e inserito nella matrice p;
con un semplice algoritmo di esplorazione in profondita` la costellazione
i viene colorata con -i-1. Le celle vuote di p sono colorate con 0. Di ogni
costellazione vengono memorizzate le dimensioni, il punto inferiore sinistro
e superiore destro del rettangolo minimo che la contiene e le coordinate del
primo punto incontrato durante la scansione.

In una seconda fase la matrice p viene scandita nuovamente. Ora ogni
costellazione incontrata viene confrontata con i tipi noti. Se e` nuova il
suo indice viene memorizzato nel vettore ind. Altrimenti viene ricolorata con
la lettera opportuna. Si noti che la _prima_ costellazione incontrata in una
classe non viene immediatamente ricolorata. La ragione sta nella funzione
copiacost(), che copia in maniera piuttosto rozza una costellazione in una
matrice temporanea, e per fare cio` identifica la costellazione tramite il
suo colore. Se accanto alla prima costellazione di un certo tipo ce ne fosse
un'altra simile, copiacost() copierebbe anche i pezzi della seconda
costellazione contenuti nel rettangolo minimo che contiene la prima.

Il lettore e` invitato a osservare come, in questo caso, l'utilizzo
delle matrici e vettori indicizzati a partire da 1 (idiomatici del PASCAL)
porti a scrivere codice decisamente farraginoso.

*)

{$R+}


function max(a,b: LongInt): LongInt;
BEGIN
	if a<b then max := b else max := a;
END;

function min(a,b: LongInt): LongInt;
BEGIN
	if b<a then min := b else min := a;
END;

CONST
	MAXDIM = 100;       (* Massima ampiezza/altezza *)
	MAXCOST = 500;      (* Massimo numero di costellazioni *)
   MAXCOSTDIV = 26;    (* Massimo numero di costelazioni _diverse_ *)
   MAXSTELLE = 160;    (* Massimo numero di stelle per costellazione *)

TYPE
	matricetemp = array[1..MAXDIM, 1..MAXDIM] of Boolean;


VAR
	p: array[1..MAXDIM, 1..MAXDIM] of Integer;	(* Punti del cielo *)
	T,U: matricetemp;	(* Matrici temporanee per memorizzare costellazioni *)
	W, H: Integer;

	(*  Queste variabili individuano un punto della costellazione (il primo
incontrato), il rettangolo minimo che contiene la costellazione e le sue
dimensioni (larghezza e altezza). *)
	x,y,minX,minY,maxX,maxY,l,a: array[1..MAXCOST] of Integer;

	ind: array[1..MAXCOSTDIV] of Integer;	(* Indice della prima costellazione
															nella classe di similitudine. *)

(*  Questa funzione scandisce una costellazione a partire dal punto x,y. La
costellazione viene colorata con colore -cost (cost e` l'indice della
costellazione). Il meccanismo utilizzato e` una semplice scansione in
profondita`. Mano a mano che la costellazione viene esplorata le variabili
maxX, minX, maxY e minY vengono aggiornate. *)

PROCEDURE scandisci(x, y, cost: Integer);
VAR
	i,j: Integer;
BEGIN

	IF p[x][y] = 1 THEN
	BEGIN
		minX[cost] := min(minX[cost], x);
		maxX[cost] := max(maxX[cost], x);
		minY[cost] := min(minY[cost], y);
		maxY[cost] := max(maxY[cost], y);
		p[x][y] := -cost;

		FOR i:=-1 TO 1 DO
			FOR j:=-1 TO 1 DO
				IF ((i<>0) OR (j<>0))
					AND (x+i>0) AND (x+i<=W) and (y+j>0) and (y+j<=H)
				THEN scandisci(x+i, y+j, cost);
	END;
END;

(* Questa funzione ricolora la costellazione cost (che si suppone colorata
	con il colore -cost-1) con il colore m partendo da un punto x,y della
	costellazione stessa. Anche in questo caso utilizziamo una scansione in
	profondita`. *)

PROCEDURE ricolora(x, y, cost, m: Integer);
VAR
	i, j: Integer;

BEGIN

	IF p[x][y] = -cost THEN
	BEGIN

		p[x][y] := m;

		FOR i:=-1 TO 1 DO
			FOR j:=-1 TO 1 DO
				IF ((i <> 0) OR (j <> 0))
					AND (x+i>0) AND (x+i<=W) AND (y+j>0) AND (y+j<=H)
				THEN ricolora(x+i, y+j, cost, m);
	END;
END;


(* Questa funzione copia il la costellazione di indice cost, colorata da
-cost, nella matrice M. Per fare cio` scandisce il rettangolo minimo che
contiene la costellazione e controlla quali caselle hanno colore -cost.
Perche' questa funzione sia corretta occorre che la costellazione copiata
abbia un colore non condiviso da nessun'altra costellazione! *)

PROCEDURE copiacost(cost: Integer; VAR M: matricetemp);
VAR
	i, j: Integer;

BEGIN
	FOR i:=0 TO l[cost]-1 DO
		FOR j:=0 TO a[cost]-1 DO
			M[i+1][j+1] := (p[minX[cost]+i][minY[cost]+j] = -cost);
END;



(* Questa funzione controlla se due costellazioni contenute nelle matrici A e
B (normalizzate in modo che la prima colonna e la prima riga di entrambe le
matrici contengano almeno un punto della costellazione) sono simili. Per fare
cio` richiede la larghezza e l'altezza della prima costellazione, e una
coppia <valore di partenza, incremento> per l'ascissa e l'ordinata della
seconda costellazione. Passando incrementi positivi o negativi e` possibile
"ribaltare" la seconda costellazione. Infine, se l'ultima variabile e`
nonzero il test viene effettuato _scambiando le coordinate x e y della
seconda costellazione_. In questo modo simuliamo un ribaltamento lungo la
diagonale. *)

FUNCTION simili(VAR P, Q: matricetemp;
						l, a, startx, incrx, starty, incry: Integer;
						invertixy: Boolean): Boolean;
VAR
	i, j: Integer;

BEGIN
	simili := TRUE;
	FOR i:=0 TO l-1 DO
		FOR j:=0 TO a-1 DO
			IF invertixy THEN
			BEGIN
				if P[i+1][j+1] <> Q[starty + j*incry+1][startx + i*incrx+1] THEN
				BEGIN
					simili := FALSE;
				END
			END
			ELSE IF P[i+1][j+1] <> Q[startx + i*incrx+1][starty + j*incry+1] THEN
			BEGIN
				simili := FALSE;
			END;
END;



VAR
	c: Char;
	i, j, k, ncost, nclassi: Integer;
	nuovo: Boolean;
	F: Text;

BEGIN

	ASSIGN(F, '');
	RESET(F);

	READLN(F, W);
	READLN(F, H);

	FOR j:=1 TO H DO
	BEGIN
		FOR i:=1 TO W DO
		BEGIN
			READ(F, c);
			p[i][j] := ord(c) - ord('0');
				(* Leggiamo l'input e lo convertiamo in 0/1 *)
		END;
		READLN(F);
	END;



	(* Prima fase: scandiamo una per una le costellazioni
		e assegnamo x, y, l e a. *)

	FOR i:=1 TO MAXCOST DO
	BEGIN
		minX[i] := High(minX[i]);
		minY[i] := High(minY[i]); (* I minimi sono inizializzati a infinito *)
	END;

	FOR j:=1 TO H DO
		FOR i:=1 TO W DO
			IF p[i][j] = 1 THEN
			BEGIN
				ncost := ncost+1;
				x[ncost] := i;
				y[ncost] := j;
				scandisci(i, j, ncost);
				l[ncost] := maxX[ncost]-minX[ncost]+1;
				a[ncost] := maxY[ncost]-minY[ncost]+1;
			END;

	(* Seconda fase: scandiamo nuovamente le costellazioni. *)

	FOR i:=1 TO ncost DO
	BEGIN
		copiacost(i, T);	(* T ora contiene la costellazione di indice i. *)
		nuovo := TRUE;	(* Partiamo assumendo che la costellazione sia nuova. *)

		FOR j:=1 TO nclassi DO
		BEGIN
			copiacost(ind[j], U); (* Esaminiamo il j-esimo tipo di
						costellazione copiando la costellazione ind[j] in U. *)

			(* Ci sono otto possibili combinazioni di incrementi lungo l'ascissa
			e l'ordinata e di inversione delle coordinate. Chiaramente dobbiamo
			prima controllare che ampiezza e altezza coincidano. *)

			IF (l[ind[j]] = l[i]) AND (a[ind[j]] = a[i])
				AND (simili(T, U, l[i], a[i], 0, 1, 0, 1, FALSE)
					  OR simili(T, U, l[i], a[i], 0, 1, a[i]-1, -1, FALSE)
					  OR simili(T, U, l[i], a[i], l[i]-1, -1, 0, 1, FALSE)
					  OR simili(T, U, l[i], a[i], l[i]-1, -1, a[i]-1, -1, FALSE))

				 OR (l[ind[j]] = a[i]) AND (a[ind[j]] = l[i])
				 AND (simili(T, U, l[i], a[i], 0, 1, 0, 1, TRUE)
					  OR simili(T, U, l[i], a[i], 0, 1, a[i]-1, -1, TRUE)
					  OR simili(T, U, l[i], a[i], l[i]-1, -1, 0, 1, TRUE)
					  OR simili(T, U, l[i], a[i], l[i]-1, -1, a[i]-1, -1, TRUE)) THEN
			BEGIN
				ricolora(x[i], y[i], i, j-1+ord('a'));
				nuovo := FALSE;
				BREAK;
			END;
		END;

		(* Se la costellazione corrente non e` classificabile, creiamo un
			nuovo tipo. *)

		IF nuovo THEN
		BEGIN
			nclassi := nclassi+1;
			ind[nclassi] := i;
		END;
	END;

	(* Infine, ricoloriamo i rappresentanti di ogni classe. *)

	FOR i:=1 TO nclassi DO
		ricolora(x[ind[i]], y[ind[i]], ind[i], i-1+ord('a'));


	ASSIGN(F, '');
	REWRITE(F);

	FOR i:=1 TO H DO
	BEGIN
		FOR j:=1 TO W DO
			IF p[j][i] = 0 THEN WRITE(F, '0') ELSE WRITE(F, chr(p[j][i]));
		WRITELN(F);
	END;
END.