Explication de l'algorithme de remplissage par inondation

Le remplissage par inondation est un algorithme principalement utilisé pour déterminer une zone délimitée connectée à un nœud donné dans un tableau multidimensionnel. C'est une ressemblance étroite avec l'outil de seau dans les programmes de peinture.

L'implémentation de l'algorithme la plus abordée est une fonction récursive basée sur la pile, et c'est de cela que nous allons parler ensuite.

Comment ça marche?

Le problème est assez simple et suit généralement ces étapes:

  1. Prenez la position du point de départ.
  2. Décidez si vous voulez aller dans 4 directions ( N, S, W, E ) ou 8 directions ( N, S, W, E, NW, NE, SW, SE ).
  3. Choisissez une couleur de remplacement et une couleur cible.
  4. Voyagez dans ces directions.
  5. Si la tuile sur laquelle vous atterrissez est une cible, remplacez-la avec la couleur choisie.
  6. Répétez 4 et 5 jusqu'à ce que vous soyez partout dans les limites.

Prenons le tableau suivant comme exemple:

texte alternatif

Le carré rouge est le point de départ et les carrés gris sont les soi-disant murs.

Pour plus de détails, voici un morceau de code décrivant la fonction:

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

Comme vu ci-dessus, mon point de départ est (4,4). Après avoir appelé la fonction pour les coordonnées de départ x = 4 et y = 4 , je peux commencer à vérifier s'il n'y a pas de mur ou de couleur sur place. Si cela est valide, je marque l'endroit avec une «couleur» et commence à vérifier les autres carrés adiacents.

En allant vers le sud, nous arriverons au point (5,4) et la fonction s'exécute à nouveau.

Problème d'exercice

J'ai toujours considéré que résoudre un (ou plusieurs) problème (s) à l'aide d'un algorithme nouvellement appris était le meilleur moyen de comprendre pleinement le concept.

Alors en voici une:

Déclaration:

Dans un tableau bidimensionnel, on vous donne n nombre d ' «îles» . Essayez de trouver la plus grande superficie d'une île et le numéro d'île correspondant. 0 marque l'eau et tout autre x entre 1 et n marque un carré de la surface correspondant à l'îlot x.

Contribution

  • n - le nombre d'îles.
  • l, c - les dimensions de la matrice.
  • les l lignes suivantes, c nombres donnant la l ème ligne de la matrice.

Production

  • i - le numéro de l'île avec la plus grande superficie.
  • A - la zone de la i 'ème île.

Ex:

Vous avez l'entrée suivante:

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

Pour lequel vous obtiendrez l'île no. 2 comme la plus grande île avec une superficie de 5 carrés.

Astuces

Le problème est assez simple, mais voici quelques conseils:

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).