38 lines
No EOL
1.1 KiB
Text
38 lines
No EOL
1.1 KiB
Text
Setup:
|
|
- Taille de la grille
|
|
- Obstacles
|
|
- Départ du rayon (avec l'orientation)
|
|
- Point d'arrivée
|
|
|
|
Déplacement:
|
|
- A chaque position on teste à gauche, à droite et en face
|
|
- Si en face, ne pas mettre de miroir et continuer
|
|
- Si a gauche ou à droite, mettre un miroir
|
|
- Si aucune solution, retour en arrirère (backtrack)
|
|
- Exceptions:
|
|
- Impossible de mettre un miroir sur un rayon déjà existant
|
|
- Impossible de viser la base du laser
|
|
- Impossible de finir dans un cul de sac (sauf si fin)
|
|
- /!\ attention aux cases vides non accessibles
|
|
|
|
Condition de fin:
|
|
- Si la pile est vide cela veut dire que toute les possibilités ont été testés et donc on renvoie la meilleure
|
|
- La meilleure solution est celle qui remplie le plus de cases vides avec le moins de miroirs
|
|
|
|
Le truc avec la pile:
|
|
- Situation:
|
|
- position i sur le plateau
|
|
- position j sur le plateau
|
|
- n le nombre de choix testés pour cette situation (de 0 à 3)
|
|
|
|
types de cases:
|
|
- 0 case vide
|
|
- -1 obstacle
|
|
- 1 laser 1
|
|
- 2 laser 2
|
|
- 3 miroir 1
|
|
- 4 miroir 2
|
|
- 10 départ nord
|
|
- 11 départ sud
|
|
- 12 départ est
|
|
- 13 départ ouest |