Βρισκόμαστε σε έναν χιονισμένο τετράγωνο κήπο διαστάσεων NxN και θέλουμε να φτιάξουμε έναν χιονάνθρωπο. Δυστυχώς το χιόνι είναι μαζεμένο σε συγκεκριμένους σωρούς μέσα στον κήπο (δεν είναι παντού). Γράψτε ένα πρόγραμμα που αποφασίζει πού πρέπει να φτιάξουμε τον χιονάνθρωπό μας ώστε να κάνουμε τον ελάχιστο δυνατό κόπο. Για λόγους απλοποίησης θεωρούμε ότι όλες οι συντεταγμένες στον κήπο είναι ακέραιες και ότι οι κινήσεις μας μπορούν να είναι μόνο πάνω-κάτω-αριστερά-δεξιά (όχι διαγώνια). Το μέγεθος του κήπου και οι τοποθεσίες των σωρών χιονιού δίνονται στο πρόγραμμα μέσω αρχείου το οποίο δίνουμε με ανακατεύθυνση στην πρότυπη είσοδο του προγράμματος. Το αρχείο θα περιέχει την διάσταση του κήπου (N) ακολουθούμενη από τις συντεταγμένες του κάθε σωρού. Παράδειγμα επιτυχούς εκτέλεσης ακολουθεί:
$ 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_1 - x_2| + |y_1 - y_2|\). Το πλήθος των σωρών δεν είναι γνωστό από πριν, οπότε διαβάστε τις συντεταγμένες μέχρι το τέλος της εισόδου σε πίνακα που μεγαλώνει δυναμικά. Μια εξαντλητική λύση δοκιμάζει κάθε θέση του κήπου και κρατά την καλύτερη. Για μεγάλο N, σκεφτείτε ότι οι δύο συντεταγμένες βελτιστοποιούνται ανεξάρτητα η μία από την άλλη.
Αριθμός στον οδηγό: Α16.17
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: lab-lab07-olaf ·
Σύνδεσμος: https://progintro.github.io/study/questions/labs/lab-lab07-olaf.html ·
Markdown (GitHub)
