Énoncé:
Vous connaissez probablement le jeu Taquin. Ici, au lieu de tuiles numérotées, nous avons sept tuiles rouges et huit tuiles bleues.
Un déplacement est indiqué par l'initiale majuscule de la direction en anglais (Left = gauche, Right = droite, Up = haut, Down = bas) dans laquelle la tuile est glissée, par exemple, en partant de la configuration $(S)$, par la séquence $LULUR$ on atteint la configuration $(E)$:
($S$)
($E$)
Pour chaque chemin, sa somme de contrôle est calculée par (pseudocode) :
$\qquad checksum = 0$
$\qquad checksum = (checksum \times 243 + m_1) mod 10^8 + 7$
$\qquad checksum = (checksum \times 243 + m_2) \mod 10^8 + 7$
$\qquad ...$
$\qquad checksum = (checksum \times 243 + m_n) \mod 10^8 + 7$
où $m_k$ est la valeur ASCII de la $k$ième lettre de la séquence de déplacement et les valeurs ASCII des déplacements sont les suivantes:
| Lettre | Valeur ASCII |
|---|---|
| $L$ | $76$ |
| $R$ | $82$ |
| $U$ | $85$ |
| $D$ | $68$ |
Pour la séquence $LULUR$ donnée ci-dessus, la somme de contrôle serait de $19761398$.
Maintenant, en partant de la configuration ($S$), trouvez tous les chemins les plus courts pour atteindre la configuration ($T$).
(S)
(T)
Quelle est la somme de toutes les sommes de contrôle pour les chemins ayant la longueur minimale ?
Lien du problème originel