Faites correspondre l'algorithme de recherche de paires?

Question

J'ai trouvé un intéressant jeu des paires correspondant à http://xepthu.uhm.vn . La règle est simple, vous devez trouver et se connecter deux pokemon identiques, mais le chemin entre eux ne soit pas bloqué et la direction ne peut pas être changé 3 fois. Voyons un exemple:

Je pense ai beaucoup sur l'algorithme pour vérifier si le chemin entre un 2 pokemon sélectionné est valide, mais parce que je suis un débutant donc je ne peux pas trouver une solution. Pouvez-vous me suggérer un en C #?

Answer 1

Ceci est essentiellement un chemin problème à trouver de théorie des graphes . Les champs de la grille sont les noeuds, et tous les champs adjacents sont reliés par une arête.

pathfinding est un problème bien connu, et il existe de nombreux algorithmes qui permettent de résoudre cela. Étant donné que votre graphique est assez petit, ici la meilleure solution est probablement juste un algorithme de force brute. Un chemin populaire algorithme de calcul est algorithme de Dijkstra.

---

Brute force: Commencez certains pokemon et explorer toutes les voies possibles pour voir si l'on conduit à un pokemon identique. Vous pouvez arrêter l'exploration d'une façon si la voie est bloquée ou a plus de 2 tours.

Vous aurez besoin d'un « pointeur » pointant vers un champ dans la grille. Le pointeur peut se déplacer à gauche, à droite, vers le haut ou vers le bas, à condition que le champ dans cette direction ne soit pas bloqué. Déplacer le pointeur vers un champ adjacent. Rappelez-vous où vous venez et combien vous tours effectués. Répétez jusqu'à ce que vous avez atteint votre destination. Backtrack si le nombre de tours atteint 3. Assurez-vous que vous ne courez pas dans les cercles.

Answer 2

Jetez un oeil à des graphes planaires. Vous devrez présenter une deuxième condition:. Pas plus de quatre noeuds peuvent être parcourus (début nœud - premier changement de direction - deuxième changement de direction - de noeud final)