Cambia il logo

Attenzione: Questo task ha un tempo limite di 10 minuti per l'invio della soluzione. Una volta richiesto un input, il timer partirà in automatico, e dopo la scadenza non sarà più possibile inviare una soluzione per quell'input. È sempre possibile richiedere un nuovo input, per cui non preoccuparti se il timer scade: dovrai semplicemente richiedere e scaricare un nuovo input.

Per aiutarti con questo task, abbiamo preparato delle tracce di soluzione, che includono solo le parti di lettura dell'input e scrittura dell'output (da tastiera e su schermo). Puoi decidere se leggere/scrivere su file decommentando le opportune righe di codice.

• Scarica la traccia in C: logo.c
• Scarica la traccia in C++: logo.cpp
• Scarica la traccia in Python: logo.py
• Scarica la traccia in Java: logo.java
• Scarica la traccia in C#: logo.cs
• Scarica la traccia in JavaScript: logo.html

Descrizione del problema

Poco prima della pubblicazione, Giorgio ha deciso di fare un'ultima modifica al logo del gioco.

Il logo consiste in una griglia $N \times M$, in cui ogni quadratino può essere bianco o nero. Giorgio ha già scelto il colore di ogni quadratino nel logo finale, e sa che per farlo è sufficiente incollare un adesivo nero rettangolare sopra al logo attuale, parallelo ai lati della griglia.

Tuttavia, per risparmiare materiale, vorrebbe usare un adesivo della minima area possibile.

Quanto vale quest'area?

Dati di input

La prima riga del file di input contiene un intero $T$, il numero di casi di test. Seguono $T$ casi di test, numerati da $1$ a $T$. Ogni caso di test è preceduto da una riga vuota.

Ogni caso di test è composto come segue:

• la prima riga contiene gli interi $N$ e $M$.
• le $N$ righe seguenti contengono $M$ caratteri ognuna, che possono essere 'N' per un quadratino nero e 'B' per uno bianco, nel logo iniziale.
• le ulteriori $N$ righe seguenti rappresentano nello stesso modo il logo finale.

Dati di output

Il file di output deve contenere la risposta ai casi di test che sei riuscito a risolvere. Per ogni caso di test che hai risolto, il file di output deve contenere una riga con la dicitura:

Case #t: x

dove t è il numero del caso di test (a partire da $1$) e il valore x è l'area minima di un adesivo che Giorgio può usare per apportare la modifica al logo, o $0$ se non è necessaria alcuna modifica.

Assunzioni

• $T = 14$, nei file di input che scaricherai saranno presenti esattamente $14$ casi di test.
• $1 \le N,M \le 300000$
• $1 \le N \times M \le 300000$

Nei primi $5$ casi di test vale $N,M \le 100$ e $N \times M \le 100$.

Esempi di input/output

---

Input:

2

3 4
BNBN
BBBN
BBNN
BNBN
BNNN
BNNN

2 2
BN
NB
BN
NB

---

Output:

Case #1: 4
Case #2: 0

---

Spiegazione

Nel primo caso d'esempio per poter cambiare il logo è sufficiente applicare un adesivo $2 \times 2$, con un'area di $4$. Con adesivi più piccoli non si riuscirebbe.

In figura sono mostrati il logo iniziale, l'adesivo applicato (in grigio) e il logo finale.

Nel secondo caso d'esempio il logo finale è uguale a quello iniziale, quindi non è necessario applicare alcuno sticker.