Gégé la grenouille

Bonjour,
Un topic a déjà été posté sur cet exercice il y a peu, mais je mets quand même l'énoncé:

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.

Sur le premier exemple, je n'ai pas de problème, mon algorithme trouve le même résultat.
Mais pour le deuxième, là ça bloque.

Je dois avoir un erreur dans mon interprétation du passage sur les cases magiques:

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).

Donc en gros, dès qu'on est sur une case magique, on peut se déplacer K fois n'importe où dans la map, et les K s'additionnent.
Si je suis ce raisonnement, j'obtiens alors pour le deuxième exemple un résultat de 45:

5 2
1 2 4 4 5
1 2 3 4 5
1 2 3 4 10
5 4 3 2 1
5 4 3 2 20
2
0 2
3 0
0 0

On a K = 2, 2 cases magiques, aux points ( 2, 0 ) et ( 3, 0 ).
Voici le chemin que je réalise pour arriver à 45:
( 0, 0 ), s = 1
( 1, 0 ), s = 3
( 2, 1 ), s = 6
( 2, 0 ), s = 10, case magique avec 2 sauts possibles
( 0, 3 ), s = 15, case magique, 3 sauts
( 4, 2 ), s = 25, 2 sauts restants
( 4, 4 ), s = 45, 1 saut restant
Fin

Merci d'avance pour votre aide

> Donc en gros, dès qu'on est sur une case magique, on peut se déplacer K fois n'importe où dans la map, et les K s'additionnent.
> Si je suis ce raisonnement, j'obtiens alors pour le deuxième exemple un résultat de 45:

Non. La grenouille peut se déplacer K fois comme une reine aux échecs. Elle doit rester sur la même ligne/colonne ou diagonale (et faire autant de déplacements qu'elle veut sur cette ligne/colonne ou diagonale).

Ah oué, ca change un peu la donne.
Merci

((( Mais malgré tout le chemin (0, 0), (1, 0), (2, 1), (3, 0), (4, 0), (4, 2), (4, 4) donne 45, et est correct selon la règle qui vient d'être précisée ...
Je me trompe ?
(En admettant que la grenouille, une fois tombée sur une case magique, peut encore se déplacer de 1 case et ne doit pas obligatoirement parcourir K cases à chaque fois)
Merci beaucoup pour vos éclaircissements )))

[Edit: Je n'ai rien dit c'est d'abord la ligne puis la colonne qui sont données en entrée, donc le chemin que j'ai donné ne passe pas sur une case magique \^\^]

Quelques petites questions sur ce sujet:
Peut-on cumuler les bonus des cases magiques ?
Est-on obligé de les utiliser consécutivement ? (si le meilleur choix consiste en un déplacement sur une case adjacente, la réponse à cette question est déterminante)

Lucas

1) On ne peut pas cumuler les cases magiques
2) On doit utiliser les K déplacements magiques consécutivement. (Cela veut dire que la grenouille peut se déplacer K fois comme une reine aux échecs, donc elle peut bien sûr faire des déplacements sur une case adjacente en tant que déplacement magique).

Je crois que j'ai jamais vu énoncé aussi incompréhensible, aussi peu clair et aussi polysémique, vous atteignez là des sommets.

Au lieu de donner des explications ABSTRAITES, ce serait beaucoup plus CLAIR d'indiquer le parcours qu'utilise la grenouille sur un EXEMPLE.

Votre premier exemple est complètement nul puisque toute la difficulté de compréhension de l'énoncé tient dans l'interprétation des cases magiques et cet exemple n'utilise PAS de cases magiques. En plus, c'est déconcertant d'avoir une valeur de K (ici 2) alors qu'il n'y a pas de cases magiques (donc on aurait K=25 que ce serait pareil).

Premier truc que je 'ai pas compris : comment se déplace la grenouille dans le cas général (hors case magique) ? L'énoncé ne le dit pas clairement : certes elle se déplace d'une case en diagonale, en ligne ou en colonne mais ça ne suffit pas à décrire ce qu'on peut comprendre : se déplace t-elle dans une case juste adjacente à sa position (comme un roi au échec ou un individu dans un labyrinthe, comme c'est le cas dans plusieurs de vos exos) ou peut-elle faire un bond vers une case non adjacente ? Je reprends votre formulation exacte :

• 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
  *

Moi je comprends (cf. la partie que j'ai mise en évidence) que la grenouille se déplace dans une case autour d'elle, comme un roi aux échecs. Même encore maintenant, je ne sais toujours pas ce que vous avez voulu dire et je ne vois pas ce qui objectivement me permettrait de le savoir.

Et votre premier exemple est totalement nul car il ne permet pas de trouver la bonne interprétation : si la grenouille se déplace sur la première ligne, case adjacente par case adjacente, elle fera un total de 1+2+3+4+5=15 mais elle peut aussi obtenir ce total sans faire par case adjacente.

Ensuite cette histoire de cases magiques. L'énoncé dit :

• 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).
  *

Je comprends pas ce que vient faire ici le "sans limitation de nombre de cases" : on nous dit que la grenouille va se déplacer K fois donc pourquoi on ajoute "sans limitation du nombre de cases" (pour moi, le nombre de cases est K donc il est pas "sans limitation") ?

Et puis au cours de ces K déplacements, la règle de la croissance stricte de la valeur de la case (qui est expliqué APRÈS dans votre énoncé ce qui est donc ambigu) s'applique-t-elle ?

Et ajoute-t-on à la somme courante les valeurs des K cases rencontrées ?

Et comment se déplace-t-on au cours des K déplacements : par exemple, si K= 3 déplacements, et si la grenouille est à la case C0, peut-elle aller à la case C1 par exemple diagonale à C0 puis de la case C1 à la case C2 sur la même ligne puis de C2 à C3 sur la même colonne (c'est un exemple) ? ou bien doit-elle faire tous ses mouvements sur la même diagonale par exemple ?

• On ne peut pas cumuler les cases magiques

• Donc concrètement, que se passe-t-il si au cours d'un des K déplacements magiques on tombe sur une autre case magique X ? La case X n'est alors pas considérée comme magique ?

• On doit utiliser les K déplacements magiques consécutivement. (Cela veut dire que la grenouille peut se déplacer K fois comme une reine aux échecs, donc elle peut bien sûr faire des déplacements sur une case adjacente en tant que déplacement magique).

• Rien compris ou plutôt compris plusieurs possibilités. Le plus simple est d'expliquer sur l'exemple 2 du sujet : un exemple, un dessin valent mieux qu'un long discours.

Autre truc qui me parait pas clair :

• 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.
  *

Pourquoi vous sentez-vous obligé de parler de la quantité de nourriture "INITIALE" ? Il y a une quantité de nourriture FINALE ?Cette quantité passe à zéro (la grenouille a ingurgidé et vidé la case) ?

Et quand le parcours de la grenouille s'arrête-t-il définitivement ? Quand une des contraintes ne peut être satisfaite ? Par exemple, est-il possible que le parcours de la grenouille s'interrompe sur une case magique ? Auquel cas votre énoncé n'est vraiment pas clair. Quand on explique les règles d'un jeu, on explique quand le jeu s'arrête.

Bref, j'ai RIEN compris à ce que cet énoncé est censé expliquer et je suis à peu près sûr que je mettrai moins de temps à le résoudre qu'à comprendre ce que vous avez voulu dire, ce qui est assez rageant.

En temps normal, la grenouille se déplace bien comme un roi aux échecs. C'est ce qu'on entend par "déplacement d'une case".

> Donc concrètement, que se passe-t-il si au cours d'un des K déplacements magiques on tombe sur une autre case
> magique X ? La case X n'est alors pas considérée comme magique ?

Si tu appliques strictement la définition d'une case magique, tu auras la réponse. (Le "compteur" sauts magiques revient à K).

> Pourquoi vous sentez-vous obligé de parler de la quantité de nourriture "INITIALE" ? Il y a une quantité de nourriture
> FINALE ?Cette quantité passe à zéro (la grenouille a ingurgidé et vidé la case) ?

oui, une fois que la grenouille a mangé la nourriture sur la case, il n'y a plus de nourriture sur la case.

Pour la fin de parcours de la grenouille, c'est justement écrit dans l'énoncé.

Pour l'exemple :
5 2
1 2 4 4 5
1 2 3 4 5
1 2 3 4 10
5 4 3 2 1
5 4 3 2 20
2
0 2
3 0
0 0

positions (ligne,colonne):
(0,0) -> a mangé 1
(1,1) -> a mangé 1+2
(1,2) -> a mangé 1+2+3
(0,2) -> a mangé 1+2+3+4, il lui reste 2 sauts magiques
(2,4) -> a mangé 1+2+3+4+10, il lui reste 1 saut magique
(4,4) -> a mangé 1+2+3+4+10+20 = 40, plus de sauts magiques
à partir de là, la grenouille ne peut plus se déplacer.

• Pour l'exemple :
  5 2
  1 2 4 4 5
  1 2 3 4 5
  1 2 3 4 10
  5 4 3 2 1
  5 4 3 2 20
  2
  0 2
  3 0
  0 0
  positions (ligne,colonne):
  (0,0) -> a mangé 1
  (1,1) -> a mangé 1+2
  (1,2) -> a mangé 1+2+3
  (0,2) -> a mangé 1+2+3+4, il lui reste 2 sauts magiques
  (2,4) -> a mangé 1+2+3+4+10, il lui reste 1 saut magique
  (4,4) -> a mangé 1+2+3+4+10+20 = 40, plus de sauts magiques
  à partir de là, la grenouille ne peut plus se déplacer.
  *

Ça commence à devenir un petit peu plus clair. Merci.

i resolved the problem with BFS algo,BUT i'm suffering with damn time limite,once the N depass 40,
can someone be kind give ME a solution thank u!
HERE is my email: lz604905@etu.unice.fr

BFS is not necessary for this problem (what is your state?). DP is enough and works well under the time limit.
(Please note also that this is a french forum)

Two years after ... :rolleyes:

Les bots font avec ce qu'ils peuvent...

Gégé le bot.

"Two years later" plutôt

Two years after [implicit : the last message] ... Rattrappage en douceur. =D