Gege la grenouille

Je pète un câble sur cet exercice depuis trop longtemps !!!! :D
J'ai tout juste réussi à faire du bourrin impératif et récursif :/
Les cases magiques je vois pas mais alors pas du tout comment
m'en débarrasser... (si quelqu'un pouvait me donner un indice,
ce serait sympa :D)

Pour repérer l'état dans laquelle se trouve la grenouille, tu peux, en plus de sa position, utiliser le nombre de sauts magiques qui lui restent, et faire un algorithme "dynamique" là dessus.

Ca j'ai fait (et de toute façon fallait bien pour avoir une réponse correcte).
Mon problème n'est pas trouver UNE solution au problème.
Mais celle qui ne me renvoie pas "limite de temps dépassée".
Je ne vois pas du tout comment m'en sortir sans tester tous les chemins à chaque
position possible. La seule solution qui ne me pose aucune problème de place est la
solution récursive (en impératif je me sens obligé de créer un tableau genre pile FIFO).
Mais que ce soit en récursif ou impératif, le temps est trop long (disons que s'il y a K coups
possibles après passage sur une case magiques, sans compter l'éventualité de retomber sur
une case magique, il y aura grosso modo (6 * N) \^K calculs à faire donc pas mal lorsque N
dépasse 10 disons).
Donc en gros s'il y a une astuce, je suis preneur. S'il y en a pas et que tout est affaire d'optimisation
je saurai me débrouiller (ou pas mais en tout cas vous ne pourrez rien pour moi :p).

Tu peux donner l'énoncé de l'exercice ?

L'énoncé pour candide :

Gégé la grenouille est très gloutonne. Elle vit dans un marais (représenté par une grille en deux dimensions), et chaque matin, ses informateurs (de leurs noms, Gaga et Gigi) lui donnent un plan du marais, avec la quantité de nourriture disponible sur chaque case.

Le but de Gégé va être d'ingurgiter le plus de nourriture possible, en se déplaçant de cases en cases dans son marais. Dès que Gégé est sur une case, elle ingurgite toute la nourriture disponible sur cette case. En temps normal, Gégé peut se déplacer d'une case à partir de la case où elle est, que ce soit horizontalement, verticalement ou en diagonale (bien sûr, sans sortir du marais). Mais certaines cases du marais sont magiques, et dès que Gégé tombe sur une telle case, elle peut se déplacer K fois (K est donné en entrée) sans limitation de nombre de cases (toujours horizontalement, verticalement ou en diagonale).

Autre caractéristique importante du déplacement de Gégé : elle ne peut aller que sur des cases dont la quantité de nourriture disponible (initiale) est strictement supérieure a la quantite de nourriture initiale de la case courante de Gege. (Autrement dit, Gege veut manger de plus en plus, elle est tres gloutonne). Entre autres choses, cela implique que Gégé ne peut jamais revenir sur des cases par où elle est déjà passée.

Ecrivez un programme pour aider Gégé à determiner la quantité maximale de nourriture qu'elle peut ingérer (elle est très très gloutonne !), en connaissant sa position initiale, la quantité de nourriture disponible sur chaque case, la position des cases magiques, et le paramètre K.

ENTREE

• Sur la première ligne : un nombre N (1- Sur les N lignes suivantes, N entiers, représentant la quantité de nourriture disponible sur chaque case. (ces nombres seront entre 0 et 100)
• Sur une ligne : le nombre M de cases magiques. (1 - Sur les M lignes suivantes : deux entiers, séparés par un espace, indiquant respectivement la ligne et la colonne d'une case magique.
• Sur la dernière ligne, deux entiers, séparés par un espace, indiquant respectivement la ligne et la colonne de la case de départ de Gégé la grenouille.

Note : toutes les coordonnées du problème commencent à 0, et seront valides. Gégé mange la nourriture disponible sur sa case de départ.

SORTIE

Un entier, la quantité maximale de nourriture que peut ingérer Gégé, si elle se débrouille au mieux.
Note : La position finale de Gégé peut être quelconque ; Gégé dispose de son hélicoptère personnel.

Quand tu fais un algorithme récursif, quels sont les paramètres de ta fonction récursive ? Est-ce que, par hasard, tu ne ferais pas plein d'appels récursifs identiques ? Si c'est le cas, une astuce (qui est en fait un véritable algorithme général), consiste à mémoriser les valeurs déjà calculées et à les renvoyées directement la deuxième fois que tu tombes sur les même paramètre d'appel de ta fonction.
(La complexité finale est ici en N\^3 * K)