Algorithme: Déterminer la forme de deux secteurs délimités par un chemin arbitraire, puis remplir un

Question

NOTE: Ceci est un problème difficile pour tous ceux qui aime les problèmes logiques, etc.

Considérons une grille à deux dimensions rectangulaire de hauteur H et largeur W. Chaque espace sur la grille a une valeur, soit 01 ou 2. Initialement, chaque espace sur la grille est un 0, à l'exception des espaces le long de chacun des quatre bords, qui sont initialement un 2. Ensuite, considérez un chemin arbitraire d'espaces de grille adjacents (horizontalement ou verticalement). Le chemin commence sur un 2 et se termine sur un 2 différent. Chaque espace le long du chemin est un 1.

Le chemin divise la grille en deux "secteurs" de 0 espaces. Il y a un objet qui repose sur un espace 0 non spécifié. Le "secteur" qui ne contient PAS l'objet doit être entièrement rempli avec 2.

définir un algorithme qui détermine les espaces qui doivent devenir 2 de 0, étant donné un réseau (liste) des valeurs (0, 1 ou 2) qui correspondent aux valeurs de la grille, en allant du haut vers le bas, puis de gauche à droite. En d'autres termes, l'élément à l'index 0 dans le tableau contient la valeur de l'espace supérieur gauche de la grille (initialement 2). L'élément à l'index 1 contient la valeur de l'espace dans la grille qui est dans la colonne de gauche, la deuxième à partir du haut, et ainsi de suite. L'élément à l'index H contient la valeur de l'espace dans la grille qui est dans la rangée du haut mais deuxième à partir de la gauche, et ainsi de suite.

Une fois l'algorithme terminé et le "secteur" vide rempli complètement avec 2 s, l'algorithme SAME doit être suffisant pour refaire le même processus. Le deuxième (et sur) temps, le chemin est toujours tiré d'un 2 à un autre 2, à travers les espaces de 0, mais la "grille" est plus petite parce que les 2 s qui sont entourés par d'autres 2 ne peuvent pas être touchés par le chemin (puisque le chemin est le long des espaces de 0).

Je remercie quiconque est capable de comprendre cela pour moi, très beaucoup. Cela ne doit pas être dans un langage de programmation particulier; en fait, le pseudo-code ou juste l'anglais est suffisant. Merci encore! Si vous avez des questions, laissez un commentaire et je préciserai ce qui doit être spécifié.

Answer 1

Il me semble un algorithme flood fill de base serait faire le travail:

• Balayez votre tableau pour la première 0 vous trouvez, puis commencer un remplissage d'inondation à partir de là, remplissant la région 0 avec un autre numéro , disons 3 - cela marquera l'un de vos "secteurs".
• Une fois cela fait, scannez à nouveau pour un 0, et inondez le remplissage à partir de là, en remplissant avec 4 cette fois.
• Pendant les deux remplissages, vous pouvez vérifier si vous avez trouvé votre objet ou non; quel que soit le remplissage que vous trouvez pendant, gardez la trace de ce nombre.
• Une fois les deux remplissages terminés, vérifiez la zone numérotée dans laquelle se trouvait l'objet. Cette fois-ci, inondez cette zone à nouveau, cette fois avec 0.
• Remplissez l'autre zone numérotée avec 2 et vous avez terminé.

Ceci fonctionnera pour n'importe quelle configuration de la grille, tant qu'il y a exactement deux secteurs 0 déconnectés l'un de l'autre; donc réappliquer le même algorithme n'importe quel nombre de fois est bien.

Edit: modifications mineures, pour vous faire gagner un remplissage d'inondation ou deux -

• Si vous ne trouvez pas votre objet dans le premier remplissage d'inondation, vous pouvez supposer que l'autre secteur a Il suffit donc de remplir à nouveau le numéro actuel avec 2 et de laisser l'autre secteur seul (puisqu'il est déjà rempli 0).
• Alternativement, si vous trouver l'objet dans la première inondation, vous pouvez directement remplir l'autre secteur avec 2, puis remplir à nouveau le premier secteur avec 0.