Cow Navigation

Η Bessie η αγελάδα έχασε τον προσανατολισμό της σε έναν λαβύρινθο διαστάσεων ~N \times N~ ~(1 \le N \le 20)~. Ξεκινάει από την κάτω αριστερή γωνία και θέλει να φτάσει στον προορισμό της, που είναι η πάνω δεξιά γωνία. Ο λαβύρινθος αποτελείται από κενά κελιά (αναπαρίστανται με E) και εμπόδια από μπάλες σανού (αναπαρίστανται με H).

Το πρόβλημα είναι ότι η Bessie δεν θυμάται αν αρχικά είναι στραμμένη προς τα πάνω (Βορρά) ή προς τα δεξιά (Ανατολή). Χρειάζεται μια ακολουθία εντολών που να εγγυάται ότι θα φτάσει στον προορισμό της, ανεξάρτητα από το ποια ήταν η αρχική της κατεύθυνση.

Κάθε βήμα (εντολή) μπορεί να είναι ένα από τα εξής:

• Να προχωρήσει ένα κελί μπροστά (Forward).
• Να στρίψει επιτόπου 90 μοίρες αριστερά (Left).
• Να στρίψει επιτόπου 90 μοίρες δεξιά (Right).

Αν η Bessie προσπαθήσει να κινηθεί μπροστά αλλά μπροστά της υπάρχει μπάλα σανού (H) ή τα όρια του λαβυρίνθου, τότε απλά παραμένει στο ίδιο κελί χωρίς να αλλάξει κατεύθυνση. Σημαντικό: Αν η Bessie φτάσει στην πάνω δεξιά γωνία (τον προορισμό της) σε κάποιο από τα δύο σενάρια, τότε παραμένει εκεί αγνοώντας τυχόν επόμενες εντολές, ενώ στο άλλο σενάριο (αν δεν έχει φτάσει ακόμα) συνεχίζει να εκτελεί τις εντολές κανονικά.

Ποιος είναι ο ελάχιστος αριθμός εντολών που πρέπει να της δώσετε ώστε να εγγυηθείτε ότι θα τερματίσει επιτυχώς και στα δύο πιθανά σενάρια;

Είσοδος

Η πρώτη γραμμή περιέχει τον ακέραιο ~N~. Ακολουθούν ~N~ γραμμές, καθεμία με ~N~ χαρακτήρες (E ή H), που περιγράφουν το λαβύρινθο. Το κάτω-αριστερό κελί (αφετηρία) και το πάνω-δεξί κελί (προορισμός) είναι πάντα E.

Έξοδος

Τυπώστε έναν ακέραιο: τον ελάχιστο αριθμό εντολών που εξασφαλίζει ότι η Bessie θα φτάσει στον προορισμό.

Παράδειγμα

input

3
EHE
EEE
EEE

output

2

Επεξήγηση παραδείγματος

Αν η Bessie δώσει την εντολή "Μπροστά" (Forward) και μετά "Δεξιά" (Right): Αν κοιτούσε Βόρεια (Πάνω), με το Forward πάει στο κεντρικό αριστερό κελί, και με το Right κοιτάει Ανατολικά. Υπάρχει άλλος συνδυασμός 2 εντολών (π.χ. Forward, Forward) που στο συγκεκριμένο πλέγμα 3x3 την φέρνει στο στόχο και στις δύο περιπτώσεις (αν κοιτούσε πάνω πάει στο (0,0)->(1,0)->(2,0) που στο παράδειγμα είναι η σωστή πορεία κλπ). Ο βέλτιστος συνδυασμός απαιτεί 2 κινήσεις.