USACO 2017 January Contest GOLD - 3 - Cow Navigation
View as PDFΗ Μπέσι ξαναβρέθηκε στη λάθος πλευρά του αχυρώνα του Γιάννη του αγρότη και, επειδή βλέπει πολύ άσχημα, χρειάζεται τη βοήθειά σου για να τον διασχίσει.
Ο αχυρώνας είναι ένα τετράγωνο πλέγμα κελιών
. Κάποια κελιά είναι άδεια και κάποια περιέχουν δέματα άχυρου, που είναι αδιάβατα. Η Μπέσι ξεκινά από το κάτω αριστερά κελί
και θέλει να φτάσει στο πάνω δεξιά κελί
.
Μπορείς να της δώσεις μια ακολουθία εντολών. Κάθε εντολή είναι μία από τις εξής: «προχώρα μπροστά κατά ένα κελί», «στρίψε 90 μοίρες αριστερά», «στρίψε 90 μοίρες δεξιά». Αν της ζητήσεις να προχωρήσει προς έναν τοίχο του αχυρώνα ή προς ένα δέμα άχυρου, δεν κινείται και απλώς περνά στην επόμενη εντολή.
Το πρόβλημα είναι ότι η Μπέσι δεν ξέρει αν ξεκινά κοιτώντας προς τα πάνω (προς το κελί ) ή προς τα δεξιά (προς το κελί
). Πρέπει να της δώσεις μία ακολουθία εντολών που θα την οδηγήσει στον στόχο και στις δύο περιπτώσεις. Μόλις η Μπέσι φτάσει στο
, αγνοεί όλες τις υπόλοιπες εντολές.
Βρες το μήκος της συντομότερης τέτοιας ακολουθίας.
Είσοδος
Η πρώτη γραμμή περιέχει τον ακέραιο .
Οι επόμενες γραμμές περιέχουν από
χαρακτήρες η καθεμία και περιγράφουν τον αχυρώνα. Ο χαρακτήρας
δηλώνει δέμα άχυρου και ο χαρακτήρας
δηλώνει άδειο κελί. Ο πρώτος χαρακτήρας της τελευταίας γραμμής είναι το κελί
και ο τελευταίος χαρακτήρας της πρώτης γραμμής είναι το κελί
.
Είναι εγγυημένο ότι τα κελιά και
είναι άδεια και ότι υπάρχει διαδρομή από άδεια κελιά που τα συνδέει.
Έξοδος
Μία γραμμή με το μήκος της συντομότερης ακολουθίας εντολών που οδηγεί την Μπέσι στον στόχο, ανεξάρτητα από το αν ξεκινά κοιτώντας πάνω ή δεξιά.
Παράδειγμα
input
3
EHE
EEE
EEE
output
9
Επεξήγηση παραδείγματος:
Μια βέλτιστη ακολουθία είναι η FRFFLFLFF (F = μπροστά, L = αριστερά, R = δεξιά).
Αν η Μπέσι ξεκινά κοιτώντας πάνω, κάνει τα εξής: προχωρά στο , στρίβει δεξιά, προχωρά στο
και μετά στο
, στρίβει αριστερά και προχωρά στο
. Έφτασε στον στόχο μετά από
εντολές και αγνοεί τις υπόλοιπες τρεις.
Αν ξεκινά κοιτώντας δεξιά, προχωρά στο , στρίβει δεξιά (κοιτά πλέον προς τα κάτω), οι δύο επόμενες εντολές «μπροστά» δεν έχουν αποτέλεσμα γιατί πέφτει πάνω στον τοίχο, στρίβει αριστερά (κοιτά πάλι δεξιά), προχωρά στο
, στρίβει αριστερά και προχωρά δύο φορές, φτάνοντας στο
με την
η εντολή.
Comments