Οδηγός Μελέτης - Εισαγωγή στον Προγραμματισμό

Α25.14 · Γεμίζοντας με χρώμα

Εξέταση Σεπτεμβρίου 2024, Θέμα 6 · Δυσκολία ★★★ · programming · Κεφάλαια: 25, 11, 12

Γεμίζοντας με Χρώμα [25 Μονάδες]

Αν έχετε χρησιμοποιήσει κάποιο πρόγραμμα ζωγραφικής στον υπολογιστή (π.χ., Paint), ίσως έχετε κάνει χρήση του “κουβά”, του εργαλείου δηλαδή που μας βοηθάει να γεμίζουμε γρήγορα κλειστές επιφάνειες χωρίς εμπόδια. Το Σχήμα 1 δείχνει ένα παράδειγμα:

 πριν         μετά
......       ......
..###.       ..###.
.#..#.  -->  .####.
.#X.#.       .####.
.###..       .###..
......       ......

Σχήμα 1: Οπτικοποίηση της διαδικασίας γεμίσματος με χρώμα. Στο σχήμα στα αριστερά επιλέξαμε την θέση (3, 2) - 3η γραμμή, 2η στήλη - για να την γεμίσουμε με χρώμα. Στο σχήμα στα δεξιά παρατηρούμε το αποτέλεσμα του γεμίσματός μας.

Σημείωση: το Σχήμα 1 του πρωτοτύπου είναι πλέγμα 6×6 με χρωματιστά κελιά· εδώ αποδίδεται με # για χρωματισμένο κελί και X για το σημείο εκκίνησης.

Για τις ανάγκες της εφαρμογής μας κάνουμε τις εξής παραδοχές: (1) έχουμε μόνο δύο χρώματα που αναπαρίστανται με 0 και 1, (2) το πρόγραμμά μας γεμίζει την εικόνα μόνο με το χρώμα 1, (3) οι εικόνες που χειριζόμαστε είναι τετραγωνικές και (4) το χρώμα μπορεί μόνο να γεμίζει επιφάνειες που επικοινωνούν ελεύθερα με το αρχικό σημείο κάνοντας μόνο κινήσεις πάνω, κάτω, αριστερά, δεξιά (όχι διαγώνια). Εάν ένα κελί περιέχει ήδη το χρώμα 1, το κελί δεν θεωρείται ελεύθερο και δρα ως “τοίχος” για το γέμισμά μας.

Γράψτε ένα πρόγραμμα το οποίο παίρνει ως όρισμα το όνομα του αρχείου που περιέχει την εικόνα και το αρχικό σημείο για γέμισμα και τυπώνει στην έξοδο την τελική εικόνα. Η πρώτη σειρά του αρχείου περιέχει την διάσταση της εικόνας, η δεύτερη σειρά τις συντεταγμένες του αρχικού σημείου και τέλος ακολουθεί η δισδιάστατη εικόνα. Παράδειγμα εκτέλεσης ακολουθεί:

$ cat picture.txt
6
3 2
000000
001110
010010
010010
011100
000000
$ ./fill picture.txt
000000
001110
011110
011110
011100
000000

Υπόδειξη

Το γέμισμα είναι φυσικά αναδρομικό: χρωματίζετε ένα ελεύθερο κελί και ζητάτε το ίδιο για τους τέσσερις γείτονές του. Η βασική περίπτωση είναι κελί εκτός ορίων ή κελί που έχει ήδη 1, κάτι που εξασφαλίζει και τον τερματισμό. Προσέξτε ότι οι γραμμές του αρχείου είναι ψηφία χωρίς κενά και ότι οι συντεταγμένες του παραδείγματος (3, 2) πρέπει να αντιστοιχιστούν σωστά σε δείκτες πίνακα (δείτε το σχήμα).

Αριθμός στον οδηγό: Α25.14 (στο κεφάλαιο) · Μόνιμο αναγνωριστικό: exam-2024-sep-q6 · Σύνδεσμος: https://progintro.github.io/study/questions/exams/exam-2024-sep-q6.html · Markdown (GitHub)