Trouver connectés éléments distincts dans un tableau à deux dimensions

Question

je pensais à ce problème depuis deux jours et n'a pas trouvé une résolution possible:

J'ai un tableau à deux dimensions et que vous voulez trouver le plus grand nombre d'éléments sont connectés (horizontal et vertical, pas en diagonale) mais aucun élément de ce groupe ne doit être dupliqué.

Exemples pour les groupes possibles:

--FG- or -F--- or ----- 
--E-- -E--- ---AF 
-BC-- CBD-- ----B 
-AD-- -A--- --CDE 

Ceci est une vue simplifiée de mon problème parce que dans la « réalité » du tableau est 6x9 et il y a trois types différents de « éléments » (LETS dire les chiffres, les lettres et symboles) avec 30 éléments distincts distincts et un élément vide (-). Dans la première passe, je vérifie chaque position et trouve tous les éléments connectés des mêmes éléments. Cela a été relativement facile à réaliser avec une fonction récursive, le 0,0 champ est en bas à gauche (une autre vue simplifiée):

12AB-1-  The check for -AB---- 
23CD23-  position 2:0  -CD---- 
2*CE55-  ("C") would  --CE--- 
#2E2*AA  result in  --E---- 
#$A23BC  this:   --A---- 
$$F1+*E      --F---- 
21C31*2      --C---- 

La vérification de la position 2: 0 « C » entraînerait un tableau 10 éléments "lettre" connectés. Maintenant, je recherche le plus grand nombre d'éléments connectés dans ce nouveau tableau qui sont distincts, de sorte que ne sont pas deux éléments en double dans le nouveau groupe. Pour la position 2: 0 cela aboutirait à 4 objets distincts maximum connectés, car vous ne pouvez pas atteindre un autre objet sans toucher à un objet qui est déjà dans le groupe (ici un autre C).

Pour mon problème, il suffit de détecter max. 6 éléments connectés différents dans le groupe 10 éléments.

Un groupe possible pour l'exemple ci-dessus serait (quand je vérifie la position 2: 1 « F »):

--B---- 
--D---- 
--C---- 
--E---- 
--A---- 
--F---- 
------- 

Je ne trouve pas un algorithme qui ferait que, comme la simple fonction récursive J'utilise pour trouver tous les éléments du même élément dans le tableau. Cela semble être beaucoup plus complexe.

Par exemple, l'algorithme doit également reconnaître qu'il n'ajoute pas le E en position 3: 4 au groupe mais le E en position 2: 3.

Je pense que l'étape intermédiaire décrit ci-dessus pour d'abord trouver alle éléments connectés d'un élément est inutiles, les mais pour le moment je fais ici et dans mon code pour rendre les choses plus clair :)

Answer 1

C'est un DFS problème. L'algorithme devrait être;

Pour chaque composant connecté, démarrez un dfs avec un map. Voici un pseudo-code:

void dfs(position pos, map<char, bool> m, int number) { 

    //if the element is seen before, quit 
    if(m[array2d[pos] == true) 
     return; 

    //it is seen now 
    m[array2d[pos]] = true; 

    //update max value 
    maxValue = max(maxValue, number); 

    //go to each neighbor 
    foreach(neighbor of pos) { 
     dfs(neighbor, m, number+1); 
    } 

    //unlock the position 
    m[array2d[pos]] = false; 
} 

Je crois que vous devriez commencer à dfs de chaque emplacement dans le tableau.

Answer 2

Parce que tout algorithme j'ai essayé ne fonctionne pas ou doit utiliser un gros tapis récursives je l'ai fait une autre façon:

Pour mon but, il suffit de vérifier pour max. 5 éléments différents connectés dans un groupe d'éléments. J'ai fait des masques (environ 60) pour toutes les combinaisons possibles pour 5 items. Voici cinq exemples.

----- ----- ----- ----- *---- 
----- ----- ----- ----- *---- 
----- ----- ----- ***-- ***-- 
----- ---*- --*-- *---- ----- 
***** ****- ****- *---- ----- 

Maintenant, je vérifie chaque composant connecté avec ces masques. Si les cinq éléments de cette position sont différents, la vérification est vraie.La position de départ réelle pour la vérification dans le masque est toujours dans l'un des quatre coins.

De cette façon, il prend moins de mémoire et moins de calculs que tous les algorithmes que j'ai essayés, mais cette résolution ne serait pas acceptable pour plus de six ou sept éléments car il y aurait beaucoup de masques.