Érigeons un barrage
Bonjour
Est-ce un problème classique ?
On dispose d'une grille N x M sur laquelle on ne peut se déplacer que de haut en bas et de droite à gauche. Chaque case de la grille a une certaine hauteur h.
Il est est impossible de passer d'une case à une autre si la différence de hauteur entre celles-ci est supérieure à une limite L. On veut faire en sorte qu'il soit impossible de traverser cette grille (c'est à dire de se rendre d'une case quelconque de la première rangée à une case quelconque de la Nième rangée) en déplaçant de la terre entre des cases mitoyennes. Quelle est la quantité minimale de terre qu'il suffit de déplacer pour bloquer le passage ?
Est-ce un problème classique ?
On dispose d'une grille N x M sur laquelle on ne peut se déplacer que de haut en bas et de droite à gauche. Chaque case de la grille a une certaine hauteur h.
Il est est impossible de passer d'une case à une autre si la différence de hauteur entre celles-ci est supérieure à une limite L. On veut faire en sorte qu'il soit impossible de traverser cette grille (c'est à dire de se rendre d'une case quelconque de la première rangée à une case quelconque de la Nième rangée) en déplaçant de la terre entre des cases mitoyennes. Quelle est la quantité minimale de terre qu'il suffit de déplacer pour bloquer le passage ?
Connectez-vous ou Inscrivez-vous pour répondre.