Εξηγήθηκε ο αλγόριθμος πλημμύρας

Το Flood fill είναι ένας αλγόριθμος που χρησιμοποιείται κυρίως για τον προσδιορισμό μιας οριοθετημένης περιοχής που συνδέεται με έναν δεδομένο κόμβο σε έναν πολυδιάστατο πίνακα. Είναι μια στενή ομοιότητα με το εργαλείο κάδου στα προγράμματα βαφής.

Η πιο προσεκτική εφαρμογή του αλγορίθμου είναι μια αναδρομική συνάρτηση που βασίζεται σε στοίβα και αυτό θα μιλήσουμε στη συνέχεια.

Πώς λειτουργεί;

Το πρόβλημα είναι πολύ απλό και συνήθως ακολουθεί αυτά τα βήματα:

  1. Πάρτε τη θέση του σημείου εκκίνησης.
  2. Αποφασίστε εάν θέλετε να πάτε σε 4 κατευθύνσεις ( N, S, W, E ) ή 8 κατευθύνσεις ( N, S, W, E, NW, NE, SW, SE ).
  3. Επιλέξτε ένα χρώμα αντικατάστασης και ένα χρώμα προορισμού.
  4. Ταξιδέψτε προς αυτές τις κατευθύνσεις.
  5. Εάν το πλακίδιο στο οποίο προσγειώνεστε είναι στόχος, εφαρμόστε το με το επιλεγμένο χρώμα.
  6. Επαναλάβετε 4 και 5 έως ότου βρεθείτε παντού εντός των ορίων.

Ας πάρουμε για παράδειγμα τον ακόλουθο πίνακα:

alt κείμενο

Το κόκκινο τετράγωνο είναι το σημείο εκκίνησης και τα γκρίζα τετράγωνα είναι οι λεγόμενοι τοίχοι.

Για περισσότερες λεπτομέρειες, ακολουθεί ένα κομμάτι κώδικα που περιγράφει τη λειτουργία:

int wall = -1; void flood_fill(int pos_x, int pos_y, int target_color, int color) 

Όπως φαίνεται παραπάνω, η αφετηρία μου είναι (4,4). Αφού καλέσω τη συνάρτηση για τις συντεταγμένες έναρξης x = 4 και y = 4 , μπορώ να αρχίσω να ελέγξω εάν δεν υπάρχει τοίχος ή χρώμα επί τόπου. Εάν αυτό είναι έγκυρο, επισημαίνω το σημείο με ένα "χρώμα" και αρχίζω να ελέγχω τα υπόλοιπα τετράγωνα.

Πηγαίνοντας νότια θα φτάσουμε στο σημείο (5,4) και η λειτουργία εκτελείται ξανά.

Πρόβλημα άσκησης

Πάντα θεωρούσα ότι η επίλυση (ή περισσότερων) προβλημάτων με τη χρήση ενός αλγορίθμου που μάθατε πρόσφατα είναι ο καλύτερος τρόπος για να κατανοήσετε πλήρως την έννοια.

Λοιπόν, εδώ είναι:

Δήλωση:

Σε έναν διδιάστατο πίνακα σας δίνεται αριθμός "νησιών" . Προσπαθήστε να βρείτε τη μεγαλύτερη περιοχή ενός νησιού και τον αντίστοιχο αριθμό νησιού. 0 σηματοδοτεί νερό και οποιοδήποτε άλλο x μεταξύ 1 και n σηματοδοτεί ένα τετράγωνο από την επιφάνεια που αντιστοιχεί στο νησί x.

Εισαγωγή

  • n - ο αριθμός των νησιών.
  • l, c - οι διαστάσεις της μήτρας.
  • οι επόμενες l γραμμές, γ αριθμοί δίνοντας στο l Th σειρά της μήτρας.

Παραγωγή

  • i - ο αριθμός του νησιού με τη μεγαλύτερη έκταση.
  • Ένα - η περιοχή του θ «ου νησιού.

Πρώην:

Έχετε τα ακόλουθα στοιχεία:

2 4 4 0 0 0 1 0 0 1 1 0 0 0 2 2 2 2 2

Για το οποίο θα πάρετε το νησί αρ. 2 ως το μεγαλύτερο νησί με έκταση 5 πλατειών.

Συμβουλές

Το πρόβλημα είναι αρκετά εύκολο, αλλά εδώ είναι μερικές συμβουλές:

1. Use the flood-fill algorithm whenever you encounter a new island. 2. As opposed to the sample code, you should go through the area of the island and not on the ocean (0 tiles).