22ος ΠΔΠ B' Φάση Λυκείου
Οι φωτιές στην Ελλάδα (fire)

Η Ελλάδα, μία ζεστή μεσογειακή χώρα με πολλές δασικές εκτάσεις, αντιμετωπίζει συχνά το καλοκαίρι πρόβλημα πυρκαγιών. Xρησιμοποιώντας κάθε τεχνολογικό μέσο, καταβάλλονται πολλές προσπάθειες για την πρόβλεψη πυρκαγιών με βάση σύνθετα μετεωρολογικά, μορφολογικά και δασολογικά δεδομένα. Mέσα στο γενικότερο πλαίσιο της προστασίας του περιβάλλοντος, πρόσφατα έχει συντελεστεί σημαντική πρόοδος στον τομέα του λογισμικού η οποία δίνει ελπίδες για την αποτελεσματική χρήση ειδικού λογισμικού για την πρόβλεψη και την αντιμετώπιση των πυρκαγιών.

Σας ζητείται να αναπτύξετε ένα πρόγραμμα σε μία από τις γλώσσες του ΙΟΙ, η οποία θα προσομοιώνει μια πυρκαγιά με βάση τη μορφολογία του εδάφους, με σκοπό να προβλέψει το μέγεθος της καταστροφής που θα προκαλούνταν αν λάμβανε χώρα η συγκεκριμένη πυρκαγιά, έτσι ώστε να μπορέσουν να εντοπιστούν οι εκτάσεις για τις οποίες θα πρέπει να επικεντρωθούν τα μέτρα πρόληψης.

Πρόβλημα

Στο μοντέλο που ακολουθούμε, δίνεται μία ορθογώνια παραλληλόγραμμη περιοχή μεγέθους \(N \times M\), όπου \(N\) και \(M\) ακέραιοι αριθμοί (\(1 \leq N, M \leq 1000\)).

Η περιοχή χωρίζεται σε ορθογώνια τμήματα εμβαδού \(1 \times 1\), κάθε ένα από τα οποία μπορεί να αναγνωριστεί αρχικά ή ως δασικό ή ως βραχώδες.

Κάθε τμήμα προσδιορίζεται από τις συντεταγμένες της άνω αριστερά (βορειοδυτικής κορυφής του \(X\) και \(Y\), όπου \(X\) και \(Y\) ακέραιοι αριθμοί (\(1 \leq X \leq N, 1 \leq Y \leq M\)). \(X\) είναι η οριζόντια συντεταγμένη και \(Y\) η κάθετη. Το τμήμα \((1, 1)\) βρίσκεται στην πάνω αριστερή γωνία του χάρτη.

Η αναγνώριση του τύπου κάθε τμήματος προσδιορίζεται με έναν χαρακτήρα. Mε τον χαρακτήρα της τελείας (.) προσδιορίζεται ένα δασικό τμήμα, ενώ με τον χαρακτήρα «παπάκι» (@) προσδιορίζεται ένα βραχώδες.

Σύμφωνα με το αρχικό μοντέλο, όταν ένα δασικό τμήμα αναφλέγεται, η φωτιά μεταφέρεται σε όλα τα διπλανά δασικά τμήματα. (Θεωρούμαι χάριν γενικότητας, ότι ο άνεμος δεν μπορεί να επιβάλει διάδοση προς μία μόνο κατεύθυνση). Διπλανά δασικά τμήματα είναι αυτά που συνορεύουν αριστερά, δεξιά, πάνω ή κάτω του αρχικώς αναφλεγόμενου (αλλά όχι διαγώνια). Η φωτιά δεν μεταφέρεται σε βραχώδη τμήματα. Τα τμήματα στα οποία η φωτιά επεκτείνεται, οδηγούν σε περαιτέρω επέκταση δεδομένου ότι λειτουργούν ως νέα τμήματα εκκίνησης πυρκαγιάς. Δεν νοείται επέκταση πυρκαγιάς σε τμήμα που έχει ήδη καεί.

Αν δίνονται οι συντεταγμένες του δασικού τμήματος όπου ξεκίνησε η φωτιά, το πρόγραμμά σας θα πρέπει να υπολογίζει το πλήθος \(C\) των δασικών τμημάτων που θα καούν, (υποθέτουμε ότι δεν υπάρχει κατάσβεση), όπου \(C\) ακέραιος αριθμός με (\(1 \leq C \leq M\cdot N\)).

Παρατήρηση: Δεν γίνεται να ξεκινήσει φωτιά σε βραχώδες ή καμένο τμήμα.

Αρχεία εισόδου

Το αρχεία εισόδου με όνομα fire.in είναι αρχείο κειμένου με την εξής δομή:

Στην πρώτη γραμμή υπάρχουν οι ακέραιοι \(N\) και \(M\) που αντιπροσωπεύουν τις διαστάσεις της περιοχής, χωρισμένοι με ένα κενό.

Στη δεύτερη γραμμή υπάρχουν δύο αριθμοί \(N_f\) και \(M_f\), οι οποίοι προσδιορίζουν τις συντεταγμένες του δασικού τμήματος όπου ξεκινάει η φωτιά, χωρισμένοι με ένα κενό.

Οι επόμενες \(M\) γραμμές περιλαμβάνουν από \(N\) ακριβώς χαρακτήρες έκαστη. Οι χαρακτήρες αυτοί είναι είτε τελεία (.) είτε «παπάκι» (@) συμβολίζοντας ένα δασικό ή ένα βραχώδες τμήμα αντίστοιχα.

Αρχεία εξόδου

Το αρχείο εξόδου με όνομα fire.out είναι αρχείο κειμένου με την εξής δομή.

Έχει μία μόνο γραμμή με ένα ακέραιο αριθμό \(C\), ο οποίος υποδηλώνειτο πλήθος των τμημάτων που υπολογίζεται ότι θα καούν, εάν δεν υπάρξει κατάσβεση.

Παραδείγματα αρχείων εισόδου - εξόδου

1^o

fire.in	fire.out
10 10 2 3 @@@@@@@@@@ @.@@@.@..@ @..@@....@ @...@@..@@ @...@....@ @...@@@@@@ @@@@@@...@ @....@@@@@ @...@@.... @@@@@@@@@@	12

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

2^o

fire.in	fire.out
10 10 5 5 .......... .......... .......... ....@..... ...@.@.... ....@..... .......... .......... .......... ..........	1

Εξήγηση παραδείγματος: Στο παράδειγμα, που ακολουθεί η φωτιά ξεκινάει από το δασικό τμήμα στην πέμπτη στήλη και την πέμπτη γραμμή και εγκλωβίζεται εκεί, γιατί το τμήμα περιβάλλεται μόνο από βραχώδη τμήματα.

Παρατηρήσεις