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
-
quante stanze ci sono nel castello
-
quant'è grande la stanza più grande
-
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.
-
Il file inizia con il numero di moduli nella direzione nord-sud e il numero
di moduli nella direzione est-ovest.
-
Nelle seguenti linee, ogni modulo viene descritto con un numero (0<=p<=15).
Questo numero è la somma di: 1 (= muro a ovest), 2 (= muro a nord),
4 (= muro a est), 8 (= muro a sud). Ciascuno dei muri interni viene perciò
definito due volte; per esempio, un muro a sud del modulo 1,1 è
anche un muro a nord del modulo 2,1.
-
Il castello contiene sempre almeno tre stanze.
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