Σημείωση: το πρωτότυπο ξεκινά με το Σχήμα 1, δύο εικόνες του λαβυρίνθου 7x7 του αρχείου
maze.txtπαρακάτω: (i) ο αρχικός λαβύρινθος, όπου ξεκινάμε στο (0, 0) και θέλουμε να φτάσουμε στο (6, 6), και (ii) μια ενδεικτική λύση, όπου επιτρέπονται κινήσεις μόνο προς τα κάτω (D) και δεξιά (R). Οι εικόνες υπάρχουν στο PDF της εξέτασης.
Σχήμα 1: Οπτικοποίηση ενός λαβυρίνθου και της λύσης του. Παρατηρήστε ότι το ρομπότ μας ξεκινάει πάντα την διαδρομή του στο (0,0) και ολοκληρώνει την διαδρομή του στο (Ν-1, Ν-1) όπου Ν η διάσταση του λαβυρίνθου.
Σε αυτό το πρόβλημα θα προγραμματίσουμε ένα ρομπότ το οποίο μπορεί να βρίσκει την έξοδο σε μια κατηγορία τετραγωνικών λαβυρίνθων, όπου η είσοδος είναι πάνω αριστερά και η έξοδος κάτω δεξιά. Για λόγους οικονομίας, το ρομπότ μας μπορεί να κινηθεί μόνο προς τα κάτω (D - Down) ή προς τα δεξιά (R - Right) σε κάθε βήμα. Το Σχήμα 1 δείχνει ένα παράδειγμα με το ρομπότ μας να βρίσκει το μονοπάτι DDDDRRRRDDRR και να φτάνει στην έξοδο.
Γράψτε ένα πρόγραμμα C που διαβάζει τον πίνακα με τα περιεχόμενα του λαβυρίνθου και τυπώνει (εφόσον υπάρχει) ένα βέλτιστο μονοπάτι για να φτάσει το ρομπότ μας στην έξοδο. Το πρόγραμμά σας πρέπει να διαβάζει τον λαβύρινθο από την πρότυπη είσοδο όπου θα δίνονται: (1) στην πρώτη γραμμή η διάσταση του τετραγωνικού πλέγματος, και (2) στην συνέχεια τα περιεχόμενα του λαβυρίνθου όπου “1” θα συμβολίζει ένα κελί με τοίχο και “0” θα συμβολίζει το κενό. Το πρόγραμμά σας πρέπει να είναι αποδοτικό σε χρονική και χωρική πολυπλοκότητα. Αφού ολοκληρώσετε το πρόγραμμά σας, καταγράψτε και εξηγήστε την πολυπλοκότητά του ως προς τον χρόνο και τον χώρο μνήμης που απαιτεί. Ακολουθούν ενδεικτικές εκτελέσεις:
$ cat maze.txt
7
0001000
0111010
0100010
0101110
0000010
0111010
0100000
$ ./robot < maze.txt
Path: DDDDRRRRDDRR
$ cat nopath.txt
7
0001000
0111010
0100010
0101110
0000010
0111110
0100000
$ ./robot < nopath.txt
No path found
Αφού κινούμαστε μόνο κάτω και δεξιά, κάθε μονοπάτι έχει ακριβώς \(2N-2\) βήματα, άρα το ερώτημα είναι μόνο αν υπάρχει. Μια αναδρομική δοκιμή όλων των διαδρομών είναι εκθετική· αντί γι’ αυτό, συμπληρώστε έναν δισδιάστατο πίνακα που λέει για κάθε κελί αν από εκεί φτάνουμε στην έξοδο (ή αποθηκεύστε τα αποτελέσματα της αναδρομής), ώστε κάθε κελί να εξετάζεται μία φορά. Προσέξτε τις περιπτώσεις όπου η αρχή ή η έξοδος είναι τοίχος και τον τρόπο που διαβάζετε γραμμές ψηφίων χωρίς κενά.
Αριθμός στον οδηγό: Α25.12
(στο κεφάλαιο) ·
Μόνιμο αναγνωριστικό: exam-2024-dec-q4 ·
Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2024-dec-q4.html ·
Markdown (GitHub)