Il sogno di Bessie#11162
Dopo che Bessie, la mucca di Farmer John, ha mangiato troppa frutta nella cucina di Farmer John, ha iniziato a fare sogni molto strani! Nel suo ultimo sogno si è ritrovata intrappolata in un labirinto a forma di griglia di piastrelle di dimensione n \times m. Inizia il suo percorso nella piastrella in alto a sinistra e vuole raggiungere la piastrella in basso a destra. Trovandosi su una piastrella, può potenzialmente spostarsi sulla piastrella adiacente in una delle quattro direzioni principali.
Ma aspetta! Ogni piastrella ha il proprio colore, e ogni colore possiede una proprietà speciale! Al solo pensiero a Bessie inizia a fare male la testa:
Se la piastrella è rossa, allora è impraticabile.
Se la piastrella è rosa, allora ci si può camminare liberamente.
Se la piastrella è arancione, allora ci si può camminare liberamente, ma dopo Bessie inizia a puzzare di arance.
Se la piastrella è blu, allora contiene piranha che permetteranno a Bessie di passare solo se puzza di arance.
Se la piastrella è viola, allora Bessie scivolerà verso la piastrella successiva nella direzione scelta (a meno che non possa attraversarla). Se anche quella piastrella è viola, Bessie continuerà a scivolare finché non si fermerà su una piastrella non viola o non si scontrerà con una piastrella impraticabile. Attraversare una piastrella durante lo scivolamento conta come una mossa. Le piastrelle viola eliminano inoltre l'odore di arance da Bessie.
Aiuta Bessie ad arrivare dalla piastrella in alto a sinistra a quella in basso a destra con il numero minimo di mosse.
Nella prima riga si trovano due numeri interi e m~(1 \le n, m \le 1000), che indicano il numero di righe e colonne del labirinto.
Nelle successive righe si trovano numeri interi che descrivono il labirinto:
Il numero indica una piastrella rossa.
Il numero indica una piastrella rosa.
Il numero indica una piastrella arancione.
Il numero indica una piastrella blu.
Il numero indica una piastrella viola.
Nella piastrella in alto a sinistra e in quella in basso a destra si troverà sempre il numero .
Stampa un singolo numero intero che indica il numero minimo di mosse che Bessie deve fare per attraversare il labirinto, oppure se ciò è impossibile.
Se non hai ancora capito bene come funzionano le piastrelle viola, l'esempio seguente illustra il loro comportamento.
In questo esempio Bessie percorre una cella in giù e due celle a destra, poi scivola per un'altra cella a destra. Successivamente percorre una cella in su, una cella a sinistra e una cella in giù, scivolando per altre due celle in giù. Alla fine percorre un'altra cella a destra. In totale ciò corrisponde a mosse (DRRRULDDDR).
Esempio 1