10ème jour

Je ne sais pas si beaucoup de gens lisent encore ce topic mais je vais quand même continuer.

Quand j'ai vu le problème du jour, je me suis dit "encore un problème avec un parcours en largeur".
Cependant, ce problème a quelques propriétés intéressantes.
- On cherche des chemins avec valeurs croissantes donc pas la peine de se soucier de la détection de cycle.
- Pour une source donnée, le nombre de chemins possibles partant de cette source est très faible.

Du coup, on peut faire un parcours en profondeur (qui est un peu plus rapide qu'un parcours en largeur) sans se soucier des sommets déjà vus. Ce qui économise une table de hash ou autre structure pour les stocker.
On obtient donc un algorithme potentiellement exponentiel alors qu'un parcours en largeur est linéaire mais en pratique, ça va plus vite.

Quelques autres optimisations que j'ai faite.
- pour la partie 1, j'utilise une table de hash pour stocker les sommets finaux (de valeur 9) accessibles depuis la source. Je ne suis pas sûr que ce soit le mieux.
- j'utilise un tableau 1 dimension pour stocker la grille. J'ajoute +1, -1, +width, -width à un index pour obtenir les sommets adjacents.
- pour éviter de tester si un voisin du sommet courant se trouve à l'intérieur de la grille, je rajoute sur les bords de la grille des caractères '#'.

Chose surprenante, la partie 2 se résout plus vite que la partie 1.

65 microsecondes pour la partie 1 + partie 2.