Rovesciare le vacche#10546
A volte Farmer John deve avere a che fare con adolescenti annoiati che di notte vengono nella sua fattoria e rovesciano le sue vacche. Una mattina si svegli e scopre che è successo di nuovo: le sue n^2 vacche hanno iniziato la notte pascolando in una perfetta griglia quadrata n \times n, ma ora alcune di esse sono sdraiate su un fianco.
Per fortuna, Farmer John ha usato dei pezzi del suo tratore e del suo caricatore per assemblare una splendida macchina chiamata Cow-Untipperator 3000, che può rovesciare contemporaneamente grandi gruppi di vacche, aiutandolo a rimettere in piedi tutte le vacche il più rapidamente possibile. Può applicare la macchina a qualsiasi "rettangolo con angolo in alto a sinistra" nella sua griglia di vacche — una sottomatrice rettangolare che contiene la vacca nell'angolo in alto a sinistra di tutta la griglia. Quando lo fa, la macchina rovescia ogni vacca in quel rettangolo: le vacche sdraiate su un fianco si rimettono in piedi, ma, purtroppo, anche le vacche che erano già in piedi cadono! In altre parole, la macchina inverte lo stato di ogni vacca nel rettangolo.
Farmer John crede che, applicando la macchina un numero sufficiente di volte a un insieme adeguato di rettangoli, alla fine potrà rimettere in piedi tutte le vacche. Aiutalo a determinare il numero minimo di applicazioni della macchina necessarie per farlo.
Osserva che applicare la macchina allo stesso rettangolo due volte è inutile, poiché il risultato non cambia lo stato delle vacche in quel rettangolo. Pertanto, ogni rettangolo con angolo in alto a sinistra deve essere considerato per l'applicazione al massimo una volta.
La prima riga contiene un numero intero n~(1 \le n \le 10). Ciascuna delle successive righe contiene una stringa di caratteri, ognuno dei quali è (la vacca è in piedi) oppure (la vacca è sdraiata su un fianco).
Stampa il numero minimo di applicazioni della macchina Cow-Untipperator 3000 necessarie a Farmer John per rimettere in piedi tutte le vacche.
In questo esempio, se Farmer John applica la macchina a tutta la griglia di vacche (che è un rettangolo con angolo in alto a sinistra valido), gli stati delle vacche cambiano come segue:
110
000
000Dopo di che, resta da applicare la macchina al rettangolo con angolo in alto a sinistra che contiene i due uno, e il problema sarà risolto. In totale saranno necessarie solo applicazioni.
Esempio 1