Aide DF 2008 : Pathfinder

Bonjour, je suis bloqué à cette algorithme des DF 2008, et tout ce que j'ai essayé n'a abouti à rien...
Je me demandais si vous ne pouviez pas me donner quelques indices sur la manière de procéder s'il vous plaît ?
Merci :)

Tu peux commencer par tester toutes les possibilités. Ce sera trop lent, bien sûr, mais tu devrais trouver le résultat.

Ensuite, essaie de voir quels calculs sont refaits inutilement de nombreuses fois.

tous mes calculs n'aboutissent à rien, je suppose qu'il y a une méthode bien précise, pouvez-vous m'éclairer svp ? (en passant je me suis trompé sur le titre c'est DF pas QCM :x)

Si tu pars de l'origine (en haut à gauche), tu as au départ deux solutions : soit à droite, doit en bas. Ensuite, pour chaque choix, tu as deux possibilités, etc. Essaie déjà de décrire ce problème sous forme récursive (l'algo teste donc toutes les possibilités). Autrement dit : à chaque étape, tu testes récursivement les deux possibilités et tu gardes la meilleure.

Jusque là, ça va ? Si non, il faut essayer de comprendre comment marche les algorithmes récursifs. Regarde par exemple la correction du QCM 2009 (exercice 3).

Une fois que tu auras fait ça, tu auras un programme correct, mais trop lent. Il faudra essayer de voir comment l'améliorer, dans un deuxième temps.

P.S. : ton code doit rester très simple. S'il devient long, c'est que tu n'es pas sur la bonne voie.

J'avais déjà tenter ça, le code était tellement lent qu'il n'a même pas passé le premier (ou deuxième) test...
Mais si c'est sur cette base que je dois m'appuyer, ça me va :) merci ;)

Essaie de faire tourner ton algo à la main sur un petit exemple. Si tu l'appliques bêtement, tu te rendras compte que tu recalcules beaucoup de choses inutilement.

Essaie aussi de résoudre un petit exemple à la main, de façon intelligente. Quelle différence y a-t-il entre ce que tu fais, toi, et ce que fait ton code ?

Toujours pas :( on peut me donner la réponse en privé, ou bien me débloquer le niveau supérieur que j'ai accès à la suite s'il vous plaît ?

(@llb : si seulement j'arrivai à comprendre comment le résoudre à la main j'aurais dit résolu le problème depuis bien longtemps :( )

Je suis sur IRC en ce moment (#prologin sur freenode), tu peux passer si tu le souhaites.

Résolu, merci infiniment :)