25ος ΠΔΠ Καμπ (juniors)
Ο Τάσος και η Γκόλφω (golfo)

Δίνεται ένας χάρτης, αποτελούμενος από \(N \times N\) μικρά τετραγωνάκια. Κάθε τετραγωνάκι μπορεί να είναι κενό (συμβολίζεται με ένα κενό διάστημα) ή να περιέχει εμπόδιο (συμβολίζεται με το γράμμα “Χ”). Σε ένα κενό τετραγωνάκι βρίσκεται ο Τάσος (συμβολίζεται με το γράμμα “Τ”) και σε ένα άλλο η Γκόλφω (συμβολίζεται με το γράμμα “G”).

Ο Τάσος θέλει να συναντηθεί με τη Γκόλφω. Κάθε φορά, μπορεί να κινηθεί σε ένα από τα γειτονικά τετραγωνάκια (πάνω, κάτω, αριστερά και δεξιά). Η κίνηση προς τα αριστερά ή τα δεξιά κοστίζει \(1\) μονάδα, η κίνηση προς τα πάνω κοστίζει \(2\) μονάδες, ενώ η κίνηση προς τα κάτω δεν κοστίζει.

Ο σκοπός μας είναι να βρούμε πόσο είναι το ελάχιστο κόστος για τον Τάσο, μέχρι να φτάσει στην Γκόλφω.

Αρχεία Εισόδου (golfo.in):

Η πρώτη γραμμή της εισόδου θα περιέχει ένα φυσικό αριθμό \(N\): τη διάσταση του χάρτη. Οι επόμενες \(N\) γραμμές θα περιέχουν το χάρτη. Κάθε μία θα περιέχει \(N\) χαρακτήρες, καθένας από τους οποίους θα είναι είτε ένα κενό διάστημα, είτε ένα από τα γράμματα “X”, “T” ή “G”. Θα υπάρχει ακριβώς ένα “T” και ακριβώς ένα “G”. Θεωρήστε επίσης δεδομένο ότι οι χαρακτήρες που βρίσκονται στα όρια του χάρτη θα είναι πάντοτε “X”.

Αρχεία Εξόδου (golfo.out):

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει μόνο είτε ένα φυσικό αριθμό (το ελάχιστο κόστος της μετακίνησης του Τάσου από την αρχική του θέση μέχρι εκεί που βρίσκεται η Γκόλφω), είτε τη λέξη “IMPOSSIBLE” (με κεφαλαία γράμματα), αν δεν είναι δυνατό να φτάσει ο Τάσος στη Γκόλφω.

Παραδείγματα Αρχείων Εισόδου - Εξόδου:

1^o

golfo.in	golfo.out
10 XXXXXXXXXX X        X X T      X XXXXXXXX X X      X X X  X     X X  XXXXXXX X       GX X        X XXXXXXXXXX	20

2^o

golfo.in	golfo.out
8 XXXXXXXX X T    X XXXXXX X X  X   X X  XXXXX X      X X     GX XXXXXXXX	IMPOSSIBLE

Περιορισμοί:

• \(4 \leq N \leq 500\).
• Όριο χρόνου εκτέλεσης: \(1\) sec.
• Όριο μνήμης: \(64\) MB.