Les feux de forêts - Collège Villey Desmeserets (Caen)

On s’intéresse à des forêts modélisées par des grilles. L’objectif est de tracer dans la forêt un chemin pour les pompiers, qui passe par une case voisine de chaque case de forêt (pour la protéger), mais qui soit le plus court possible (afin de limiter la surface de forêts à couper).
On pourra s’intéresser à des forêts rectangulaires, à des pompiers capables de protéger les cases le long du chemin ou aussi en diagonale (voire que en diagonale !), et même des pompiers capables de protéger les cases à distance 2 du chemin. On peut aussi diversifier la forme des forêts (grille triangulaire, hexagonale,...) ou la forme du chemin, en autorisant les embranchements et les impasses, en imposant que le chemin décrive une boucle. Quel que soit le choix que vous faites, on aimerait avoir les solutions pour des tailles de grilles variées.