Joseph Marin – Épreuve régionale 2025

Niveau 4 ⋅ Validation weight: 20%

Énoncé

Joseph Marchand et son nouvel allié connaissent dès à présent l'emplacement de la tour de contrôle ciblée ! Ils tentent alors de s'y rendre de toute urgence. Cependant, le seul moyen de s'y rendre est d'y aller en sous-marin, et la topologie de la zone rend le trajet difficile...

La ville est représentée par une grille de $\mathtt{hauteur}$ lignes et $\mathtt{largeur}$ colonnes. Votre objectif est de vous déplacer de votre point de départ, le coin en haut à gauche, de coordonnées $(1, 1)$, à l'emplacement de la tour de contrôle, dans le coin en bas à droite, aux coordonnées $(\mathtt{largeur}, \mathtt{hauteur})$, et cela le plus rapidement possible.

La topologie de la zone est représentée par une matrice d'entiers, chaque entier représentant l'altitude de la zone. Le sous-marin se déplace de case en case adjacente (diagonales interdites). Il existe deux types de déplacement faisables par le sous-marin :

  • Se déplacer d'un point à un point adjacent, d'altitude égale ou inférieure. Cela prend 100 secondes, quelles que soient les altitudes des deux points.
  • Se déplacer d'un point à un point adjacent plus élevé. Cela prend 200 secondes, plus le carré du différentiel d'altitude entre les deux points.

Cependant, Joseph Marin, le conducteur du sous-marin, étant un conducteur expérimenté, il peut réussir à gagner en vitesse sous certaines conditions. Notemment, lors d'une chute d'altitude, Joseph Marin peut conserver son altitude actuelle le temps d'un déplacement. Ainsi :

  • Après avoir effectué un déplacement du premier type et perdu de l'altitude, si le prochain déplacement nécessite de regagner autant ou moins d'altitude que l'altitude tout juste perdue, alors ce second déplacement peut se faire en 100 secondes, plutôt que 200 plus le différentiel d'altitude.
  • Après avoir effectué un déplacement du premier type et perdu de l'altitude, si le prochain déplacement nécessite de regagner plus d'altitude que l'altitude tout juste perdue, alors le différentiel d'altitude considéré partira du point précédent.

Aidez Joseph Marin à déterminer le temps minimal pour atteindre la tour de contrôle.

Entrée

L’entrée contiendra :

  • Sur la première ligne, un entier : hauteur, la hauteur de la liste du relief.
  • Sur la ligne suivante, un entier : largeur, la largeur de la liste du relief.
  • Sur les lignes suivantes, une liste de hauteur éléments : relief, la liste représentant le relief.
    • Une ligne par élément de la liste : une liste de largeur entiers séparés par des espaces.

Sortie

Affichez, sur une ligne, un entier : le temps minimal pour atteindre la tour de contrôle.

Contraintes

  • $1 \le \mathtt{hauteur} \le 25$
  • $1 \le \mathtt{largeur} \le 25$
  • $-10\,000 \le \mathtt{relief}_i \le 10\,000$

Contraintes de performance

  • $1 \le \mathtt{hauteur} \le 1\,000$
  • $1 \le \mathtt{largeur} \le 1\,000$

Contraintes d'exécution

Utilisation mémoire maximum
100000 kilo-octets
Temps d'exécution maximum
1000 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
3
3
1 2 1
2 3 1
3 4 3
Exemple de sortie
602
Commentaire

Dans cet exemple, nous allons observer deux trajets.

Les deux chemins commencent par se rendre au point $(2,1)$. Ce déplacement prendra $200 + (2 - 1)^2 = 201$ secondes, car nous devons monter d'un mètre d'altitude.

Nous allons commencer par suivre le chemin rouge :

Nous nous rendons ensuite au point $(3,1)$. Comme nous nous trouvons à une altitude supérieure, le temps pour atteindre ce point sera de $100$ secondes. Puis nous atteignons le point $(3, 2)$, qui est à une altitude similaire et que nous atteindrons en $100$ secondes. Enfin, nous arrivons jusqu'à la tour de contrôle. Cependant, celle-ci se trouve à une altitude supérieure, nous devons donc effectuer une ascension qui nous prendra $200 + (3 - 1)^2 = 204$ secondes. Le temps final sera donc de $605$ secondes.

Maintenant, considérons le chemin vert :

Nous atteignons le point $(2, 2)$. Comme il se situe à une altitude supérieure, nous devons effectuer une ascension qui nous prendra $200 + (3 - 2)^2 = 201$ secondes. Pour atteindre le point $(3, 2)$, Joseph Marin doit descendre. Cependant, expert en conduite de sous-marin, il aperçoit une élévation du relief et maintient son altitude à $3$ pendant une étape au lieu de plonger, afin d'éviter de devoir effectuer une remontée. Le temps mis pour effectuer cette opération est donc de $100 + 100$ secondes.

Le temps final pour atteindre la tour de contrôle par le chemin vert est de $602$ secondes et est donc meilleur que le chemin rouge prenant $605$ secondes. Il n'est ici pas possible de trouver un chemin atteignant la tour de contrôle en moins de $602$ secondes, il faut donc afficher $602$.

avec pompe

Exemple d'entrée
1
8
10 4 11 3 5 12 2 10
Exemple de sortie
950
Commentaire

Il n'y a ici qu'un seul chemin possible. On s'intéresse ici simplement à savoir en combien de temps Joseph peut effectuer ce chemin.

Le chemin commence par une descente immédiatement suivie d'une remontée. Pour atténuer le coût de la montée, Joseph peut conserver son altitude à $10$, et atteindre le sommet d'altitude $11$ en $100 + 200 + (11 - 10)^2 = 301$ secondes.

Un second pic se situe trois étapes plus loin. Cependant, cette fois-ci, Joseph ne peut pas conserver son altitude à $11$ aussi longtemps. Il peut cependant conserver son altitude à $11$ à la place de redescendre à $3$ afin de ne pas avoir à effectuer la montée $3 \to 5$. Il arrive alors au sommet d'altitude $12$ en $100 + 100 + 200 + (12 - 5)^2 = 449$ secondes supplémentaires.

Finalement, en maintenant son altitude à $12$ plutôt que de descendre à $2$, Joseph évite d'effectuer une dernière montée et atteint la tour de contrôle en $100 + 100 = 200$ secondes supplémentaires.

Au total, Joseph effectue le parcours complet en $301 + 449 + 200 = 950$ secondes.

img from paint