Jeu de connexion numérique en C/C++ ?

Jeu - Supposons qu'il existe un tableau carré n × n. Parmi eux, certains carrés sont vides, certains sont solides et certains carrés non solides sont définis par des entiers 1, 2, 3,... Chaque nombre entier contient ou occupe exactement deux cases différentes sur le plateau. La tâche du joueur est de relier les deux occurrences de chaque nombre entier sur le plateau à l'aide de chemins simples qui mettent en œuvre uniquement des mouvements horizontaux et verticaux. Deux chemins différents ne peuvent pas se croiser. Aucun chemin ne peut contenir de blocs solides (les blocs solides ne sont autorisés sur aucun chemin). Enfin, tous les carrés non pleins doivent être remplis par des chemins.

Algorithme - Pour construire un puzzle aléatoire efficace avec une taille de tableau n × n donnée, nous générons d'abord des chemins aléatoires simples et mutuellement disjoints sur le tableau noir. Si certains blocs isolés sont toujours en dehors de tous les chemins générés, marquez ces blocs isolés comme solides (interdits). Ensuite, nous fournissons les extrémités du chemin et une liste de carrés pleins comme puzzle.

Nous générons donc d’abord une solution, puis calculons le puzzle en fonction de cette solution. Les chemins et les carrés pleins séparent n × n plaques. Nous implémentons et trouvons la structure de données pour générer cette partition. La structure de données gère un sous-ensemble de l'ensemble des n^2 cases de l'échiquier.

Pseudocode

• Positionnez les cases (a, b) et (c, d) au hasard sur l'échiquier, de telle sorte que -

  • (a, b) et (c, d) soient voisines l'une de l'autre, Et ni

  • (a, b) ni (c, d) n'appartiennent à aucun chemin généré jusqu'à présent. si dans Tableau entier, renvoie FAILURE /* Ici, (a​​, b) et (c, d) sont les deux premiers carrés du nouveau chemin établir. */

• Union de deux arbres de recherche d'union, qui contient (a, b) et (c, d).

• Répétez jusqu'à ce que le chemin actuel puisse être étendu -

  Renommer (a, b) = (c, d).

Trouver un carré adjacent aléatoirement (c, d) (a, b) tel que -

• (c, d) n'appartient à aucun chemin généré jusqu'à présent (y compris le chemin actuel)

• Le seul voisin (c, d) sur le chemin actuel de la construction partielle est (a, b).

Si aucun voisin (c, d) n'est trouvé, le chemin ne peut pas être prolongé davantage, brisant ainsi le cycle

Sinon, les deux (a, b) et (c, d) appartiennent à et trouvez l'arbre.

Définissez les drapeaux de point final des deux blocs situés au début et à la fin du nouveau chemin.

Retour au SUCCÈS

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!