AlgoNTUA Day 1: Φίλη μου αγαπημένη

View as PDF

Submit solution

All submissions

Best submissions

Points: 10 (partial)

Time limit: 1.0s

Memory limit: 64M

Author:

jbalatos

Problem types

Φίλη μου αγαπημένη

Αφού τελείωσαν με τα εστιατόρια, η Κατερίνα και η Γιούλα ήθελαν να βρεθούν για να ανταλλάξουν τις κριτικές τους. Όμως λίγο το κακό σήμα, λίγο τα στενά της Ζωγράφου, λίγο η συνωνυμία των μαγαζιών, τα κορίτσια κατάλαβαν διαφορετικό σημείο συνάντησης. Δίνεται ένας χάρτης, αποτελούμενος από $N \times N$ $N \times N$ μικρά τετραγωνάκια. Κάθε τετραγωνάκι μπορεί να είναι κενό (συμβολίζεται με ένα κενό διάστημα) ή να περιέχει εμπόδιο (συμβολίζεται με το γράμμα " $X$ $X$ "). Σε ένα κενό τετραγωνάκι βρίσκεται η Κατερίνα (συμβολίζεται με το γράμμα " $T$ $T$ ") και σε ένα άλλο η Γιούλα (συμβολίζεται με το γράμμα " $G$ $G$ ").

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

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

Δεδομένα εισόδου

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

Δεδομένα εξόδου

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει μόνο είτε ένα φυσικό αριθμό (το ελάχιστο κόστος της μετακίνησης της Κατερίνας από την αρχική της θέση μέχρι εκεί που βρίσκεται η Γιούλα), είτε τη λέξη " $IMPOSSIBLE$ $I M P O S S I B L E$ " (με κεφαλαία γράμματα), αν δεν είναι δυνατό να φτάσει η Κατερίνα στη Γιούλα.

Περιορισμοί

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

Παραδείγματα εισόδου - εξόδου

1o

STDIN

10
XXXXXXXXXX
X X
X T X
XXXXXXXX X
X X X
X X X
X XXXXXXX
X GX
X X
XXXXXXXXXX

STDOUT

2o

STDIN

8
XXXXXXXX
X T X
XXXXXX X
X X X
X XXXXX
X X
X GX
XXXXXXXX

STDOUT

IMPOSSIBLE

Comments

There are no comments at the moment.