Problem
Eric lavora come guardia di sicurezza all'università, quindi dopo una giornata di lavoro gira per l'edificio e spegne le luci di notte.
L'edificio si sviluppa su n piani e presenta due corpi scala a sinistra ea destra. Ci sono m stanze su ogni piano lungo il corridoio che collega le scale sinistra e destra. In altre parole, l'edificio può essere rappresentato come un rettangolo con n righe e m + 2 colonne, dove la prima e l'ultima colonna — scale e m colonne nel mezzo — camere.
Eric è ora in piedi al primo piano sulle scale a sinistra. Vuole spegnere le luci ovunque, mentre non vuole salire al piano di sopra prima di aver spento tutte le luci del piano attuale. Ovviamente Eric deve essere nella stanza per spegnere le luci. Eric trascorre un minuto salendo le scale di un piano o andando alla stanza/scale successiva dalla stanza successiva o scale sullo stesso piano. Spegnere le luci nella stanza in cui si trova Eric non richiede tempo.
Aiuta Eric a trovare il tempo minimo per spegnere tutte le luci dell'edificio.
Tieni presente che Eric non è obbligato a tornare alla sua posizione originale e inoltre non è tenuto a visitare le stanze in cui le luci sono già spente.
Inserimento:
La prima riga contiene due numeri interi n e m (1 ≤ n ≤ 15, 1 ≤ m ≤ 100) — rispettivamente il numero di piani e il numero di stanze su ciascun piano.
Le n righe successive contengono una descrizione dell'edificio. Ogni riga contiene una stringa di zeri e uno di lunghezza m + 2 che descrivono un piano (scale a sinistra, poi m stanze, poi scale a destra), dove 0 significa che le luci sono spente e 1 significa che le luci sono accese. I piani sono riportati in ordine dall'alto verso il basso, in particolare l'ultima riga descrive il primo piano.
Il primo e l'ultimo carattere di ogni riga descrivono le scale, quindi sono sempre 0.
Uscita:
Stampa un numero — il tempo minimo possibile necessario per spegnere tutte le luci.
Esempi:
| Input |
Uscita |
2 2
0010
0100 |
5 |
3 4
001000
000010
000010 |
12 |
Spiegazioni:
Nel primo esempio, Eric andrà prima nella stanza 1 al primo piano, e poi — alla stanza 2 al secondo piano utilizzando qualsiasi scala.
Nel secondo esempio, andrà prima nella quarta stanza al primo piano, salirà di un piano sulle scale a destra, entrerà nella quarta stanza al secondo piano, salirà di nuovo le scale a destra, andrà alla seconda stanza all'ultimo piano.