Τίτλος	Διαδρομές σε λαβύρινθο
Problem ID	multilab

Δίνεται ένας λαβύρινθος και Ν συγκεκριμένα σημεία (check points) μέσα σε αυτόν. Να βρεθεί το μήκος της συντομότερης διαδρομής από την αφετηρία (πάνω αριστερά τετράγωνο) στο τέρμα (κάτω δεξια τετράγωνο) που όμως περνά από όλα τα check points.

Η είσοδος του προγράμματος (standard input) θα είναι ως εξής: Η πρώτη γραμμή θα έχει τον αριθμό Ν των γραμμών του λαβυρίνθου. Θα ακολουθούν N γραμμές με την περιγραφή του λαβυρίνθου, με χαρακτήρες.

• Ο λαβύρινθος δίνεται με τους χαρακτήρες '.' (τελεία, dot) για τα επιτρεπόμενα τετράγωνα που σχηματίζουν τους διαδρόμους, '#' (δίεση, hash) για τα μη επιτρεπόμενα τετράγωνα (τοίχους) και '*' (αστεράκι, star) για τα check points. Ο,τιδήποτε άλλο θεωρείται μη επιτρεπτή θέση. Πάντα θα υπάρχουν τα check points της αφετηρίας και του τέρματος (πάνω αριστερά και κάτω δεξιά).
• Ο λαβύρινθος είναι σε σχήμα ορθογωνίου.
• Ο λαβύρινθος δε θα έχει πάνω από 25 γραμμές και δε θα έχει πλάτος πάνω από 70 χαρακτήρες
• Θα υπάρχουν τουλάχιστον 2 και το πολύ 20 check points
• Οι δυνατές κινήσεις στο λαβύρινθο είναι μόνο πάνω, κάτω δεξιά και αριστερά (δηλαδή οχι διαγώνια) και η καθεμιά έχει κόστος (ή μήκος) 1.
• Το μήκος μιας διαδρομής είναι ο αριθμός των βασικών κινήσεων που κάνουμε στο λαβύρινθο ακολουθώντας τη διαδρομή.

Η έξοδος του προγράμματος (standard output) θα είναι το μήκος της ζητούμενης συντομότερης διαδρομής, ή -1 αν δεν υπάρχει τέτοια διαδρομή.

Παράδειγμα:

Είσοδος:

3
*..........
##########.
##########*

12

Δεύτερο Παράδειγμα:

Είσοδος:

5
*.........#####
#######.#######
#......*...*..#
#######.#######
#.............*

26