25ος ΠΔΠ B' Φάση Γυμνασίου
Ανασύσταση της Βοιβηίδος λίμνης (karla)

Η λίμνη Kάρλα (Βοιβηίς) στη Θεσσαλία, δημιουργήθηκε από τα νερά των απορροών των γύρω ορεινών όγκων έως τον Πηνειό ποταμό, αλλά και των πλημμυρικών νερών του Πηνειού, που βρίσκεται υψηλότερα από τη λίμνη. Το 1962 ξεκίνησε η αποξήρανσή της των \(130.000\) στρεμμάτων λίμνης χωρίς όμως να δημιουργηθεί παραγωγική καλλιεργήσιμη γη, ενώ αντίθετα σοβαρές υπήρξαν οι περιβαλλοντικές επιπτώσεις. Στις μέρες μας το Ελληνικό κράτος έχοντας αντιληφθεί τη σημασία των υγροβιότοπων προχωρά στην ανασύσταση περίπου \(78.000\) στρεμμάτων λίμνης.

Mε μεγάλη απλοποίηση η συγκεκριμένη περιοχή μπορεί να προσεγγισθεί με ένα πλέγμα \(N\times N\) ισοϋψών τετραγώνων. Kάθε τετράγωνο χαρακτηρίζεται από το υψόμετρό του. Στο παρακάτω σχήμα (αριστερά) φαίνεται ένα παράδειγμα με \(N=5\).

Ανάλογα με τον όγκο των απορροών, τα τετράγωνα που έχουν υψόμετρο ίδιο ή χαμηλότερο από το ισοδύναμο υψόμετρο¹ των απορροών πλημμυρίζουν. Για παράδειγμα, για απορροές ισοδύναμου υψομέτρου \(4\) τα τετράγωνα που πλημμυρίζουν φαίνονται με κόκκινο στο προηγούμενο σχήμα (δεξιά). Είναι δηλαδή τα τετράγωνα με υψόμετρο μικρότερο ή ίσο του \(4\). Τα υπόλοιπα τετράγωνα που δεν πλημμυρίζουν σχηματίζουν πέντε ενοποιημένες περιοχές, δηλαδή πέντε περιοχές αποτελούμενες από τετράγωνα που κάθε ένα συνορεύει (μοιράζεται μία από τις πλευρές του) με κάποιο άλλο. Οι πέντε ενοποιημένες περιοχές φαίνονται στο παραπάνω σχήμα (δεξιά) με χρώματα: γκρί, γαλάζιο, πορτοκαλί, κίτρινο και πράσινο.

Πρόβλημα

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

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

Τα αρχεία εισόδου με όνομα karla.in είναι αρχεία κειμένου με την εξής δομή: Η πρώτη γραμμή περιέχει δύο ακέραιους αριθμούς \(N\) και \(M\) χωρισμένους με ένα κενό διάστημα (\(1 \leq N, M \leq 100\)), όπου \(N\) η διάσταση του πλέγματος και \(M\) το ισοδύναμο ύψος απορροών. Kάθε μία από τις επόμενες \(N\) γραμμές περιέχει \(N\) ακέραιους αριθμούς \(x_{ij}\) χωρισμένους ανά δύο με ένα κενό διάστημα (\(1 \leq x_{ij} \leq 1000\)), τα υψόμετρα των τετραγώνων της αντίστοιχης γραμμής του πλέγματος.

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

Τα αρχεία εξόδου με όνομα karla.out είναι αρχεία κειμένου με την εξής δομή: Έχουν ακριβώς μία γραμμή που περιέχει έναν ακέραιο αριθμό \(K\) (\(0 \leq K \leq N^2\)). Ο αριθμός αυτός εκφράζει το πλήθος των ενοποιημένων περιοχών που δεν πλημμυρίζουν.

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

1^o:

karla.in	karla.out
5 4 6 8 2 6 2 3 2 3 4 6 6 7 3 3 2 7 2 5 3 6 8 9 5 2 7	5

2^o:

karla.in	karla.out
10 6 9 9 9 9 9 9 9 9 9 9 9 8 8 8 8 8 8 8 8 9 9 8 7 7 7 7 7 7 8 9 9 8 7 6 6 6 6 7 8 9 9 8 7 6 5 5 6 7 8 9 9 8 7 6 5 5 6 7 8 9 9 8 7 6 6 6 6 7 8 9 9 8 7 7 7 7 7 7 8 9 9 8 8 8 8 8 8 8 8 9 9 9 9 9 9 9 9 9 9 9	1

Mέγιστος χρόνος εκτέλεσης: \(2\) sec.