IOI'94 - Giorno 1 - Problema 2: Il castello

     1   2   3   4   5   6   7
   #############################
 1 #   |   #   |   #   |   |   #
   #####---#####---#---#####---#   
 2 #   #   |   #   #   #   #   #
   #---#####---#####---#####---#
 3 #   |   |   #   #   #   #   #   
   #---#########---#####---#---#
 4 # ->#   |   |   |   |   #   #   
   #############################  (Figura 1)

#  = Muro
|  = Nessun muro
-  = Nessun muro
-> = Indica il muro che va rimosso secondo l'output dell'esempio.
La Figura 1 mostra la mappa di un castello. Scrivete un programma che calcoli
  1. quante stanze ci sono nel castello
  2. quant'è grande la stanza più grande
  3. quale muro rimuovere per creare la stanza più grande possibile.
Il castello è diviso in m * n (m<=50, n<=50) moduli quadrati. Ogni modulo può avere da zero a quattro muri perimetrali.

Dati di input

La mappa del castello si trova nel file INPUT.TXT sottoforma di numeri, uno per ciascun modulo. INPUT.TXT per il nostro esempio: 
4
7
11 6 11 6 3 10 6
7 9 6 13 5 15 5
1 10 12 7 13 7 5
13 11 10 8 10 12 13

Dati di output

Nel file OUTPUT.TXT ci saranno tre linee: la prima contiene il numero delle stanze, la seconda contiene la superficie della stanza più grande (contata come numero di moduli) e l'ultima contiene un suggerimento su quale muro abbattere al fine di ottenere la stanza di superficie più grande possibile; quest'ultimo dato viene indicato dal numero di riga, dal numero di colonna e dalla direzione (N=nord/S=sud/E=est/W=ovest) del muro. Nel nostro esempio  ("4 1 E" è solo una delle molte possibili soluzioni: il programma deve comunque solo produrne una): 
5
9
4 1 E

Strutture dati fondamentali


Informazioni relative ai moduli

Il programma mantiene un array modulo[i,j] che fornisce informazioni sui muri adiacenti al modulo di coordinate i,j. Inoltre, mantiene un secondo array stanza[i,j] che per ogni modulo dice a quale stanza appartiene. Le stanze sono numerate da 1, e 0 significa che non si è ancora determinato a quale stanza appartenga quel modulo.

Informazioni relative alle stanze

Per ciascuna stanza, vengono conservate alcune informazioni. Innanzitutto, l'array dim[s] contiene la dimensione della stanza s (si noti che la dimensione potrebbe essere inferiore a quella reale se la stanza s non è ancora stata completamente "determinata"). Inoltre, la matrice ad[t] fornisce informazioni sull'adiacenza fra la stanza corrente (quella che stiamo colorando) e la stanza t. Più precisamente, ad[t].adiacenti dice se le due stanze sono adiacenti (per quanto ne sappiamo in questo momento); se ciò è vero, gli altri campi di ad[t] contengono informazioni su un muro che le rende adiacenti.

Informazioni relative all'ottimo corrente

Le variabili globali max e maxs contengono la massima dimensione di una stanza fra quelle fino ad ora trovate, e la massima somma fra le dimensioni di stanze adiacenti (fra quelle fino ad ora trovate). Inoltre maxa contiene le informazioni necessarie a determinare quale muro abbattere per ottenere maxs.
 

Algoritmo


L'algoritmo si basa sulla procedura assegna(i,j) che effettua la determinazione di una componente connessa (per diffusione). Più precisamente, la procedura opera come segue:

  1. Assegna al modulo i,j il numero della stanza corrente. Incrementa la dimensione della stanza corrente, e se questa supera max aggiorna quest'ultimo.
  2. Visita ricorsivamente i moduli adiacenti a i,j non separati da esso da un muro.
  3. Per i moduli separati da i,j da un muro, se essi hanno già una stanza assegnata, inserisce le informazioni relative all'adiacenza fra la stanza corrente e quella trovata nell'array ad. Questo viene fatto solo la prima volta (se si scopre un altro modo per rendere adiacenti le due stanze, esso viene ignorato).
La procedura assegna(i,j) viene chiamata dalla assegnastanze che opera come segue:
  1. Se c'è ancora qualche modulo non assegnato, incrementa il numero di stanze, e invoca assegna(i,j) su un (qualunque) modulo libero.
  2. Al termine, controlla le informazioni di adiacenza contenute nell'array ad[t] e, se scopre che può migliorare maxs, lo assegna (e assegna anche maxa).

Valutazione e discussione


Ogni modulo viene visitato una sola volta da assegna(i,j). La procedura assegna scandisce comunque molte volte i moduli, quando deve cercare il primo modulo libero, ma questo non comporta un aumento sensibile del tempo di calcolo.
Potrebbe sembrare più naturale il calcolo di una matrice bidimensionale di adiacenza per determinare, solo alla fine, il valore di maxs. Questo, però, non sembra fattibile date le limitazioni del Turbo Pascal sulle dimensioni delle variabili statiche. Infatti, considerato che (grossolanamente) ci potrebbero essere 50*50=2500 stanze, e che per ogni coppia di stanze occorrono almeno due bytes per memorizzare le coordinate di un muro, e un byte addizionale per la direzione (da usarsi anche come booleano per l'adiacenza), servirebbero 2500*2500*3 bytes (o 2500*2500*3/2 bytes, se memorizziamo solo una metà della matrice).