Εισαγωγή
Σχεδιάζεις να χτίσεις ένα δεντρόσπιτο στο δάσος κοντά στο σπίτι σου, ώστε να μπορείς να βλέπεις την ανατολή και τη δύση του ήλιου.
Έχεις αποκτήσει δεδομένα από μια τοπική εταιρεία τοπογραφικών μετρήσεων, που δείχνουν το ύψος κάθε δέντρου σε κάθε ορθογώνιο τμήμα του χάρτη.
Πρέπει να αναλύσεις κάθε πλέγμα του χάρτη για να βρεις καλά δέντρα για το δεντρόσπιτό σου.
Ένα καλό δέντρο είναι ταυτόχρονα:
- ψηλότερο από κάθε δέντρο στα ανατολικά και στα δυτικά, ώστε να έχεις την καλύτερη δυνατή θέα στις ανατολές και τις δύσεις του ήλιου.
- πιο κοντό από κάθε δέντρο στα βόρεια και στα νότια, ώστε να ελαχιστοποιήσεις το σκαρφάλωμα στα δέντρα.
Οδηγίες
Η αποστολή σου είναι να βρεις τα πιθανά δέντρα όπου θα μπορούσες να χτίσεις το δεντρόσπιτό σου.
Η εταιρεία δεδομένων παρέχει τα δεδομένα ως πλέγματα που δείχνουν τα ύψη των δέντρων.
Οι γραμμές του πλέγματος αντιπροσωπεύουν την κατεύθυνση ανατολής-δύσης, και οι στήλες αντιπροσωπεύουν την κατεύθυνση βορρά-νότου.
Ένα αποδεκτό δέντρο θα είναι το μεγαλύτερο στη γραμμή του, ενώ ταυτόχρονα το μικρότερο στη στήλη του.
Ένα πλέγμα μπορεί να μην έχει καθόλου καλά δέντρα.
Ή μπορεί να έχει ένα, ή ακόμη και αρκετά.
Ορίστε ένα πλέγμα που έχει ακριβώς ένα υποψήφιο δέντρο.
↓
1 2 3 4
|-----------
1 | 9 8 7 8
→ 2 |[5] 3 2 4
3 | 6 6 7 1
- Η γραμμή 2 έχει τις τιμές 5, 3, 2 και 4. Η μεγαλύτερη τιμή είναι 5.
- Η στήλη 1 έχει τις τιμές 9, 5 και 6. Η μικρότερη τιμή είναι 5.
Άρα το σημείο στο [2, 1] (γραμμή: 2, στήλη: 1) είναι εξαιρετικό μέρος για ένα δεντρόσπιτο.
Οι θέσεις στη Rust ξεκινούν από το 0
Κατά σύμβαση, τα περιεχόμενά των διατεταγμένων ακολουθιών τιμών στη Rust αριθμούνται (τους αποδίδεται θέση) ξεκινώντας από το 0. Αυτό ισχύει ανεξάρτητα από το τι λέει η υπόλοιπη περιγραφή της άσκησης σε αυτό το README, όπως αναφορές σε θέσεις που ξεκινούν από το 1, οπότε θα χρειαστεί να αφαιρέσεις το 1 για να μετατρέψεις αυτούς τους αριθμούς θέσης σε αριθμούς θέσης στη Rust.
Σημείωση αποδοτικότητας
Αυτή η άσκηση χρησιμοποιεί ένα διάνυσμα από διανύσματα για να αποθηκεύσει το περιεχόμενο πινάκων. Ενώ αυτή η άσκηση έχει σχεδιαστεί για να βοηθήσει τους μαθητές να κατανοήσουν βασικές έννοιες σχετικά με τα διανύσματα, όπως την πρόσβαση σε στοιχεία με θέση, και ότι οι εμφωλευμένοι τύποι δεδομένων είναι επιτρεπτοί, το διάνυσμα από διανύσματα είναι υποβέλτιστη επιλογή για άλγεβρα πινάκων υψηλών επιδόσεων και για κάθε παρόμοια αποδοτική επεξεργασία μεγαλύτερων όγκων δεδομένων.
Η λεπτομερής εξήγηση αυτής της αναποτελεσματικότητας είναι πέρα από το πεδίο αυτής της άσκησης και αυτής της μαθησιακής διαδρομής γενικότερα. Αυτή η πτυχή είναι γνωστή ως τοπικότητα της κρυφής μνήμης και μπορείς να βρεις μια καλή εισαγωγή σε αυτήν κάνοντας κλικ σε αυτόν τον σύνδεσμο, αν θέλεις να μάθεις περισσότερα για τις λεπτομέρειες της σύγχρονης αρχιτεκτονικής υπολογιστών.
