La poltrona di Korrot

Il robot Korrot deve trovare una poltrona su cui sedersi.
Korrot vive in una scacchiera NxM, con le righe numerate da 1 a N (dal basso verso l’alto) e le colonne numerate da 1 a M (da sinistra a destra).
Parte dalla riga più in basso (la riga 1) e deve raggiungere la poltrona sulla riga più in alto (la riga N).
Korrot può spostarsi in tutte le direzioni tranne che in diagonale.
La figura sottostante illustra una possibile disposizione iniziale di Korrot (K) e della poltrona (P) in una scacchiera con N=5 e M=6.

Figura 1.
Percorso: AAAAS (poltrona)

Korrot ha un modo particolare di raggiungere l’ambita poltrona.
Parte da una delle caselle sulla riga 1 e procede verso l’alto fino alla riga N, poi prosegue il suo percorso verso destra o verso sinistra in direzione della poltrona.
Nell’esempio mostrato, il percorso scelto da Korrot prevede 4 passi verso l’alto e uno verso sinistra ed è rappresentato dalle lettereAAAAS.

Purtroppo, Korrott ha una nemica di nome Maggie che dissemina la scacchiera di scomodi ostacoli.
Se Korrot si trova di fronte a un ostacolo, deve aggirarlo.
Nell’affrontare gli ostacoli bisogna ricordare che, per come è programmato, Korrot prova sempre ad andare verso l’alto per raggiungere l’ultima riga e poi, muovendosi su questa (a destra o sinistra), prova a raggiungere la poltrona.
Ecco quindi come si comporta Korrot:

• Se incontra un ostacolo mentre cerca di andare verso l’alto, Korrot devia a destra.
• Se però si trova nella colonna più a destra (la colonna M) devia a sinistra per non cadere dalla scacchiera.
• In entrambi i casi tenta di risalire non appena può.
• Se Korrot è già arrivato alla riga più in alto, evita gli ostacoli con una mossa verso il basso (spostandosi quindi temporaneamente sulla riga N-1) e rientra sulla riga N appena possibile (eventualmente per sedersi sull’ambita poltrona).
• Se Korrot trova un ostacolo nella casella dove vorrebbe deviare, va in uno stato di confusione totale e rinuncia per sempre all’amata poltrona.
• Inoltre Korrot rinuncia alla poltrona anche se è costretto a ritornare sui suoi passi.

Ecco alcuni esempi del comportamento di Korrot (gli ostacoli sono rappresentati dal simbolo O, la casella finale presenta il simbolo P sottolineato).

Figura 2.
Percorso: ADAADDAADA (poltrona)

Figura 3.
Percorso: DAA (confusione: è programmato per andare a destra ma a destra trova un ostacolo)

Figura 4.
Percorso: SAAD (confusione: costretto a tornare sui propri passi)

Figura 5.
Percorso: AAAASBSSSAS (poltrona)

Figura 6.
Percorso: AAAASBSS (confusione: non è sull’ultima riga e quindi non può andare in basso)

Scrivere un programma che riproduca il comportamento di Korrot stampandone il corrispondente percorso.

Dati di input

Il file input.txt contiene sulla prima riga in ingresso i due interi positivi N (il numero delle righe nella scacchiera) e M (il numero delle colonne nella scacchiera), separati da uno spazio.
La seconda riga del file contiene le posizioni iniziali, rispettivamente di Korrot e della poltrona, rappresentate ognuna da un solo intero positivo (soltanto l’indice di colonna nella scacchiera: sappiamo che la riga nella scacchiera è 1 per Korrott e N per la poltrona).
Ciascuna delle righe seguenti nel file è riferita ad un ostacolo.
Su ciascuna riga del file si trovano due interi positivi (indice di riga e indice di colonna nella scacchiera, separati da uno spazio) che rappresentano la posizione dell’ostacolo considerato.

Dati di output

Il programma, dopo aver letto l’input, deve scrivere in output due righe.
Sulla prima riga le mosse fatte da Korrot, usando le abbreviazioni

Sulla riga successiva, il programma deve scrivere il risultato finale:

 

Assunzioni

• 1 < M, N < 210

 

Esempi di input/output

 

Note

• I cinque esempi corrispondono alle Figure 1..5.
• Korrot è un personaggio completamente inventato: non esiste alcuna creatura che strisci alla ricerca di una poltrona ed eviti gli ostacoli svoltando sempre a destra.