Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό
Α16.25 · Χτίζοντας έναν Χιονάνθρωπο
Πρόγραμμα: olaf.c (25 μονάδες)
Βρισκόμαστε σε έναν χιονισμένο τετράγωνο κήπο διαστάσεων ΝxN και Θέλουμε να φτιάξουμε έναν χιονάνθρωπο. Δυστυχώς το χιόνι είναι μαζεμένο σε συγκεκριμένους σωρούς μέσα στον κήπο (δεν είναι παντού). Γράψτε ένα πρόγραμμα που αποφασίζει που πρέπει να φτιάξουμε τον χιονάνθρωπό μας ώστε να κάνουμε τον ελάχιστο δυνατό κόπο. Για λόγους απλοποίησης θεωρούμε ότι όλες οι συντεταγμένες στον κήπο είναι ακέραιοι και ότι οι κινήσεις μας μπορούν να είναι μόνο πάνω-κάτω-αριστερά-δεξιά (όχι διαγώνια). Το μέγεθος του κήπου και οι τοποθεσίες των σωρών χιονιού δίνονται στο πρόγραμμα μέσω αρχείου του οποίου το όνομα θα είναι το πρώτο όρισμα του προγράμματος. Το αρχείο θα περιέχει την διάσταση του κήπου (Ν) ακολουθούμενη από τις συντεταγμένες του κάθε σωρού. Παράδειγμα επιτυχούς εκτέλεσης ακολουθεί:
$ gcc -o olaf olaf.c
$ cat map.txt
10
1 1
6 7
2 8
7 2
$ ./olaf map.txt
We will position the snowman on (4, 4) with a minimum cost of 22.
Παρακάτω βλέπουμε την οπτικοποίηση της επιλογής μας - ο χιονάνθρωπος βρίσκεται στην θέση “καρότο” ενώ οι σωροί με τα χιόνια απεικονίζονται με τους κύκλους. Από τους δύο πάνω σωρούς παρατηρούμε ότι χρειαζόμαστε 6 βήματα για να φτάσουμε τον χιονάνθρωπο ενώ από τους δύο κάτω χρειαζόμαστε 5 - σύνολο (6 + 6 + 5 + 5 =) 22. Παρατηρήστε ότι μπορεί να υπάρχουν πάνω από μία βέλτιστες τοποθετήσεις, χρειάζεται να βρούμε μόνο μία από αυτές. Για λόγους απλότητας ο χιονάνθρωπος μπορεί να τοποθετηθεί πάνω σε έναν σωρό (και τα βήματα που απαιτούνται σε αυτήν την περίπτωση είναι 0).
Υπόδειξη
Το κόστος μιας θέσης είναι το άθροισμα των αποστάσεων Manhattan |x - xi| + |y - yi| από όλους τους σωρούς. Μια λύση ωμής βίας δοκιμάζει κάθε κελί του κήπου, αλλά κοστίζει O(N²·K)· παρατηρήστε ότι οι δύο συντεταγμένες ανεξαρτητοποιούνται και ρωτήστε τον εαυτό σας ποιο σημείο ελαχιστοποιεί το άθροισμα απολύτων αποστάσεων σε μία διάσταση. Ελέγξτε ότι οι συντεταγμένες είναι μέσα στον κήπο και ότι υπάρχει τουλάχιστον ένας σωρός.
Αριθμός στον οδηγό: Α16.25
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2023-fall-ex3-q4 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2023-fall-ex3-q4.html ·
Markdown (GitHub)