"The Bride" si trova a dover attraversare nel minor tempo possibile il castello della misteriosa O-Ren Ishii. Il castello ha forma rettangolare con M x N stanze e i suoi quattro lati sono identificati con i quattro punti cardinali: NORD (alto), EST (destra), SUD (basso), OVEST (sinistra). Tale castello è fornito di M ingressi sul lato OVEST e M uscite sul lato EST. Ogni stanza interna del castello comunica con quattro altre stanze, situate rispettivamente a NORD, EST, SUD e OVEST. Le stanze lungo il perimetro esterno del castello hanno chiaramente meno stanze comunicanti. Ogni stanza è univocamente identificata dalla coppia (i, j), in quanto collocata all'incrocio tra la riga i-esima e la colonna j-esima di stanze del castello (1 ≤ i ≤ M e 1 ≤ j ≤ N).
"The Bride" intende attraversare il castello da OVEST a EST nel minor tempo possibile, entrando in una delle M stanze esterne nel lato OVEST del castello e uscendo da una delle M stanze esterne nel lato EST del castello. Appena entra nel castello, il suo cronometro con tempi parziali si azzera. Quando si trova in un certa stanza, non può tornare indietro (verso OVEST), mentre le altre tre direzioni (NORD, EST, SUD) sono permesse. Purtroppo il castello nasconde delle insidie nelle sue stanze. In ogni stanza attraversata "The Bride" è costretta ad affrontare un combattimento di diverso grado di difficoltà, perdendo minuti preziosi. Il suo cronometro viene esclusivamente aggiornato dopo tali combattimenti, incrementandolo con la quantità di minuti persi a combattere. Se "The Bride" passa più volte in una data stanza, è costretta a ripetere il combattimento, conteggiando di nuovo quei minuti.
Aiuta "The Bride" a determinare qual è il minor tempo possibile per attraversare il castello di O-Ren Ishii!
Il file input.txt contiene sulla prima riga i due interi positivi M e N separati da uno spazio. Le successive M righe (per i = 1, 2, ..., M) contengono ciascuna N numeri interi positivi (per j = 1, 2, ..., N) separati da uno spazio e rappresentano le stanze (i,j) del castello. In particolare, l'intero in posizione j di tale riga i rappresenta il numero di minuti necessari per il combattimento di "The Bride" nella stanza (i,j).
Il programma, dopo aver letto il file di input, deve scrivere una sola riga nel file output.txt contenente il tempo minimo di attraversamento del castello. Il tempo va descritto fornendo il numero totale di minuti impiegati a tal fine da "The Bride".
File input.txt
5 5
90 5 10 23 44
1 8 8 21 32
4 15 9 10 11
3 12 5 21 23
82 13 6 37 45
File output.txt
47
(Nota: corrisponde al percorso 1, 8, 8, 9, 10, 11.)
File input.txt
1 4
5 1 1 2
File output.txt
9
Nota: "The Bride" e O-Ren Ishii sono personaggi del film "Kill Bill vol.1", di Quentin Tarantino.