Το Καλό το Μονοπάτι - path [25 Μονάδες]
Στην προσπάθειά του να τονώσει την τουριστική κίνηση, ο Ελληνικός Ορειβατικός Σύλλογος (ΕΟΣ) αποφάσισε να χρηματοδοτήσει ένα καινούριο έργο για την δημιουργία νέων, ήσσονος προσπαθείας μονοπατιών που να απευθύνονται σε αρχαρίους. Ο ΕΟΣ έχει ήδη πρόσβαση σε αναλυτικούς χάρτες με την δυσκολία της κάθε υποδιαδρομής. Το μόνο που λείπει για να προχωρήσει στην χάραξη των μονοπατιών, είναι ένα σύστημα το οποίο δοθέντος ενός χάρτη να υπολογίζει εύκολα και γρήγορα το μονοπάτι ελαχίστου κόστους. Ως συνήθως, το τμήμα μας προσφέρθηκε να βοηθήσει—αμισθί εννοείται—για την ταχεία διεκπεραίωση του έργου. Το Σχήμα 1 δείχνει έναν χάρτη-παράδειγμα από το φαράγγι του Βίκου:
| [10] | 13 | 10 | 11 | 10 |
| [10] | 10 | 10 | 18 | 10 |
| [15] | 42 | 42 | 42 | 42 |
| [17] | [5] | [5] | [5] | 14 |
| 10 | 10 | 10 | [10] | [10] |
Σχήμα 1: Ένας 5x5 χάρτης του ΕΟΣ με τα κόστη κάθε υποδιαδρομής να φαίνονται σε κάθε κελί του πλέγματος. Η διαδρομή ελαχίστου κόστους εικονίζεται σκιαγραφημένη. Παρατηρήστε πως η διαδρομή αποφεύγει τα κελιά υψηλού κόστους (τα 42 αναπαριστούν τον Βοϊδομάτη).
Σημείωση: στο πρωτότυπο η διαδρομή είναι χρωματισμένα κελιά· εδώ σημειώνεται με
[ ].
Θεωρούμε πως όλοι οι χάρτες του ΕΟΣ είναι ένα τετραγωνικό πλέγμα και πως σε κάθε κελί του υπάρχει ένας ακέραιος αριθμός που αναπαριστά το κόστος της κάθε υποδιαδρομής. Για λόγους απλοποίησης, θεωρούμε πως σε κάθε χάρτη ο στόχος είναι να χαράξουμε ένα μονοπάτι από την άνω αριστερή γωνία του χάρτη μέχρι την κάτω δεξιά. Επίσης, κατά την διάρκεια της χάραξης επιτρέπονται μόνο μονοπάτια τα οποία κινούνται προς τα κάτω ή προς τα δεξιά (όχι προς τα πάνω / αριστερά / διαγώνια).
Γράψτε ένα πρόγραμμα το οποίο παίρνει ως όρισμα το όνομα του αρχείου που περιέχει τον χάρτη (διάσταση καθώς και τα κόστη κάθε υποδιαδρομής) και υπολογίζει το μονοπάτι ελαχίστου κόστους. Αν η διάσταση του πλέγματος είναι Ν, ποια η χρονική και χωρική πολυπλοκότητα της λύσης σας (8/25 της βαθμολογίας); Παράδειγμα εκτέλεσης ακολουθεί:
$ cat map.txt
5
10 13 10 11 10
10 10 10 18 10
15 42 42 42 42
17 5 5 5 14
10 10 10 10 10
$ ./path map.txt
Minimum Cost: 87
Minimum Cost Path: 10 -> 10 -> 15 -> 17 -> 5 -> 5 -> 5 -> 10 -> 10
Η εξαντλητική αναδρομή δοκιμάζει εκθετικά πολλά μονοπάτια· παρατηρήστε ότι το ελάχιστο
κόστος για να φτάσετε σε ένα κελί εξαρτάται μόνο από το κελί από πάνω και το κελί από
αριστερά, οπότε μπορείτε να γεμίσετε έναν πίνακα N×N γραμμή-γραμμή (δυναμικός
προγραμματισμός). Για να τυπώσετε και το μονοπάτι, ξεκινήστε από την κάτω δεξιά γωνία
και ακολουθήστε προς τα πίσω από πού ήρθε κάθε ελάχιστο. Το N διαβάζεται από το αρχείο,
άρα ο πίνακας χρειάζεται δυναμική δέσμευση· προσέξτε και την πρώτη γραμμή/στήλη.
Αριθμός στον οδηγό: Α25.15
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2025-sep-q5 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2025-sep-q5.html ·
Markdown (GitHub)