# TP — Le Donjon du Dragon
## Contexte
Vous jouez à un RPG en vue du dessus. Vous venez d'entrer dans un donjon représenté par une **grille de n lignes et m colonnes**.
Chaque case de la grille contient une quantité d'or :
- Une valeur **positive** : de l'or à ramasser 🪙
- Une valeur **négative** : un piège qui vous coûte de l'or 💀
**Règles du jeu :**
- Vous commencez en haut à gauche : case `(0, 0)`
- Vous devez atteindre la sortie en bas à droite : case `(n-1, m-1)`
- Vous ne pouvez vous déplacer **que vers la droite ou vers le bas**
- Vous souhaitez **maximiser l'or total ramassé**
**Exemple de grille 3×4 :**
```
[ 3, -1, 4, 1 ]
[ 5, 9, -2, 6 ]
[ -3, 2, 8, -5 ]
```
Un chemin possible : (0,0)→(1,0)→(1,1)→(1,2)→(2,2)→(2,3) → or = 3+5+9-2+8-5 = **18**
Est-ce le meilleur chemin ? C'est ce que vous allez découvrir.
## Partie 1 — Comprendre le problème
**Question 1.** Sur la grille ci-dessus, listez tous les chemins possibles de `(0,0)` à `(2,3)` en ne se déplaçant que vers la droite ou vers le bas. Combien y en a-t-il ?
**Question 2.** Pour chaque chemin, calculez l'or total ramassé. Quel est le chemin optimal ?
**Question 3.** Pour une grille de dimensions `n × m`, combien y a-t-il de chemins possibles en tout ? *(Indice : c'est une formule combinatoire.)*
## Partie 2 — Formulation récursive
Notons `donjon(i, j)` l'or maximum qu'on peut ramasser depuis `(0, 0)` jusqu'à `(i, j)`.
**Question 4.** Quels sont les cas de base de cette fonction récursive ? *(Pensez aux bords de la grille.)*
**Question 5.** Écrivez la relation de récurrence générale pour `donjon(i, j)` quand `i > 0` et `j > 0`.
**Question 6.** Implémentez la version naïve `donjon_naif(grille, i, j)` :
```python
def donjon_naif(grille, i, j):
# À compléter
pass
# Test
grille = [
[ 3, -1, 4, 1],
[ 5, 9, -2, 6],
[-3, 2, 8, -5]
]
n, m = len(grille), len(grille[0])
print(donjon_naif(grille, n-1, m-1)) # doit afficher 22
```
## Partie 3 — Version Top-Down (mémoïsation)
**Question 7.** La version naïve recalcule-t-elle des sous-problèmes plusieurs fois ? Pour répondre, ajoutez un compteur d'appels et testez sur la grille ci-dessus.
**Question 8.** Implémentez `donjon_memo(grille)` avec mémoïsation :
```python
def donjon_memo(grille):
n = len(grille)
m = len(grille[0])
memo = {}
def donjon(i, j):
# À compléter
pass
return donjon(n - 1, m - 1)
```
**Question 9.** Vérifiez que vous obtenez le même résultat que la version naïve.
## Partie 4 — Version Bottom-Up (tableau)
**Question 10.** Remplissez à la main le tableau `t[i][j]` représentant l'or maximum qu'on peut ramasser **depuis `(0,0)` jusqu'à `(i,j)`** pour la grille de l'exemple.
**Question 11.** Implémentez `donjon_bottom_up(grille)` :
```python
def donjon_bottom_up(grille):
n = len(grille)
m = len(grille[0])
tableau = [[0] * m for _ in range(n)]
# Initialiser tableau[0][0]
# Initialiser la première ligne (on ne peut aller que vers la droite)
# Initialiser la première colonne (on ne peut aller que vers le bas)
# Remplir le reste du tableau
# À compléter
return tableau[n - 1][m - 1]
```
**Question 12.** Vérifiez que vous obtenez le même résultat que les versions précédentes.
## Partie 5 — Bonus : retrouver le chemin optimal
**Question 13.** *(Bonus)* Modifiez `donjon_bottom_up` pour qu'elle retourne non seulement la valeur optimale, mais aussi **la liste des cases du chemin optimal**.
*(Indice : une fois le tableau rempli, remontez depuis `(n-1, m-1)` vers `(0,0)` en choisissant à chaque étape la case voisine (gauche ou haut) qui a la plus grande valeur.)*
```python
def donjon_chemin(grille):
# À compléter
# Retourne (valeur_max, chemin)
# chemin = liste de tuples (i, j) de (0,0) à (n-1, m-1)
pass
```
---
Auteur : Florian Mathieu
Licence CC BY NC
Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d'Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International.