Navigazione bovina#10552
Bessie si trova di nuovo sul lato sbagliato della fattoria di Farmer John e, poiché ha una vista molto scarsa, ha bisogno del vostro aiuto per attraversare la fattoria.
La fattoria è rappresentata da una griglia quadrata n \times n di celle, alcune delle quali sono vuote e altre contengono balle di fieno invalicabili. Bessie inizia il movimento dall'angolo in basso a sinistra (cella ) e vuole raggiungere l'angolo in alto a destra (cella ). Potete controllare il suo movimento impostando una sequenza di comandi, ciascuno dei quali è uno dei seguenti: «avanti», «gira a sinistra di gradi» oppure «gira a destra di gradi». È richiesto impostare la sequenza più breve possibile di comandi che la porti a destinazione.
Se date a Bessie il comando di muoversi fuori dalla griglia (cioè contro il muro della fattoria) o dentro una balla di fieno, lei non si sposta e semplicemente passa a eseguire il comando successivo nella sequenza.
Sfortunatamente, Bessie non sa in quale direzione sia inizialmente rivolta: verso l'alto (in direzione della cella ) o verso destra (in direzione della cella ). Dovete impostare la sequenza più breve possibile di comandi che porti Bessie all'obiettivo indipendentemente dalla sua direzione iniziale. Non appena raggiunge l'obiettivo, ignorerà tutti i comandi rimanenti.
La prima riga contiene il numero n~(2 \le n \le 20). Ciascuna delle successive righe contiene una stringa di esattamente caratteri che descrive la fattoria. Il primo carattere dell'ultima riga corrisponde alla cella , e l'ultimo carattere della prima riga corrisponde alla cella .
Ogni carattere è pari a , che indica una balla di fieno, oppure a , che indica una cella vuota.
Si garantisce che le celle e siano vuote. Inoltre, si garantisce che esista un percorso composto solo da celle vuote dalla cella alla cella .
Stampate la lunghezza della sequenza più breve di comandi che porti Bessie all'obiettivo indipendentemente dal fatto che inizi il movimento rivolta verso l'alto o verso destra.
In questo esempio la sequenza di comandi "Forward, Right, Forward, Forward, Left, Forward, Left, Forward, Forward" porterà Bessie a destinazione indipendentemente dalla sua direzione iniziale.
Esempio 1