Ξεχασμένα Αντικείμενα

Εκφώνηση

Ο Δημήτρης, μέσα στο τρέξιμο για να οργανώσει το Algo NTUA έχει παρατήσει αντικείμενά του γύρω γύρω στα κτίρια της ΗΜΜΥ (ευτυχώς αυτά δεν ξεπερνάνε τα 10). Και τώρα πρέπει να τα μαζέψει. Για κακή του τύχη, η Αγγελική ήδη τον κυνηγάει ότι έχει καθυτερήσει, οπότε θα πρέπει να τα μαζέψει όσο πιο γρήγορα γίνεται. Για καλή του όμως τύχη, έχει αρκετά καλή χωρική αντίληψη και μνήμη ώστε να θυμάται ακριβώς που έχει αφήσει τι αλλά και τι εμπόδια υπάρχουν στη σχολή. Έχει φτιάξει δηλαδή έναν νοητό χάρτη.

Δωσμένου αυτού του χάρτη βοηθήστε τον Δημήτρη να συλλέξει τα αντικείμενά του όσο πιο γρήγορα γίνεται.

Μορφή εισόδου

Η είσοδος θα έχει πολλαπλά test cases. Κάθε test case θα έχει την ακόλουθη μορφή: Η πρώτη γραμμή θα περιέχει 2 ακέραιους αριθμούς, ~h, w~, το ύψος και το πλάτος του χάρτη αντίστοιχα. Οι επόμενες ~h~ γραμμές περιέχουν ~w~ χαρακτήρες που αντιστοιχούν στα κελιά του χάρτη. Κάθε κελί μπορεί να είναι ένας από τους ακόλουθους χαρακτήρες:

• @ Το σημείο από όπου πρέπει να ξεκινήσει ο Δημήτρης
• ~ Σφουγγαρισμένο σημείο. Ο Δημήτρης δεν μπορεί να περάσει από εκεί χωρίς να εκνευρίσει τις καθαρίστριες οι οποίες θα τον κηνυγήσουν, αποτρέποντάς τον από το να μαζέψει τα πράγματά του.
• # Ένα πλήθος από πρωτοετής φοιτητές ΗΜΜΥ. Το πλήθος είναι πολύ πυκνό για να μπορεί ο Δημήτρης να περάσει ανάμεσά τους
• . Άδειος διάδρομος. Από εδώ προφανώς μπορεί να περάσει με άνεση
• * Κάποιος από τους πολλούς γνωστούς του που αν τον εντοπίσουν θα του πιάσουν την κουβέντα και δε θα τον αφήνουν να φύγει για να μαζέψει τα αντικείμενά του. Για να αποφύγει να τον σταματήσει κάποιος γνωστός θα πρέπει να βρίσκεται τουλάχιστον ένα τετράγωνο μακριά (και στις 8 κατευθύνσεις)
• ! Ένα από τα αντικείμενά του. Ο Δημήτρης προφανώς δε θέλει να αφήσει κανένα αντικείμενο πίσω

Ο Δημήτρης μπορεί να ταξιδέψει μόνο στις 4 διευθύνσεις πάνω, κάτω, αριστερά και δεξιά. Δεν μπορεί δηλαδή να κινηθεί διαγώνια. Κάθε μετακίνηση από ένα κελί σε κάποιο γειτονικό του παίρνει 1 λεπτό. Η συλλογή των αντικειμένων γίνεται πρακτικά στιγμιαία.

Το μέγιστο μέγεθος κάθε χάρτη είναι 50 x 50. Η είσοδος τελειώνει με έναν πίνακα 0 x 0 ο οποίος πρέπει να αγνοηθεί.

Μορφή Εξόδου

Για κάθε test_case εκτυπώστε, σε ξεχωριστή γραμμή, τα λεπτά που χρειάζεται ο Δημήτρης για να συλλέξει τα αντικείμενά του. Αν δεν είναι εφικτό να τα συλλέξει όλα, επιστρέψτε -1.

Παράδειγμα

Είσοδος

7 7
~~~~~~~
~#!###~
~...#.~
~~....~
~~~.@~~
.~~~~~~
...~~~.
10 10
~~~~~~~~~~
~~!!!###~~
~##...###~
~#....*##~
~#!..**~~~
~~....~~~~
~~~....~~~
~~..~..@~~
~#!.~~~~~~
~~~~~~~~~~
0 0

Έξοδος

10
32