Franchissement – Épreuve régionale 2024

Énoncé¶

Durant une visite chez les dieux, Jøsëf Marchand se rend à Helheim pour rencontrer Hel. Cette dernière lui confie de précieuses missives secrètes concernant des signes du commencement du Ragnarök. Jøsëf Marchand se met alors immédiatement en chemin vers Ásgard pour transmettre les missives à Odin.

Cependant, pour quitter Helheim, il doit traverser le Gjölle, un fleuve mortel qui relie Helheim au reste des mondes grâce aux racines de l'Yggdrasil

Heureusement, lors de l'une des précédentes tentatives d'invasion des Jötunn, ces derniers ont disposé des rochers dans la rivière pour pouvoir la traverser.

Jøsëf Marchand ne maitrisant pas le seiðr (magie nordique) il ne peut pas augmenter sa taille pour atteindre celle d'un Jötunn. Il est donc contraint d'effectuer des sauts pour franchir la rivière.

Pour assurer sa sécurité, il s'impose des contraintes :

• à cause du vent et des courants très forts, Jøsëf ne peut pas se déplacer sur un rocher situé plus au nord ou plus à l'ouest que celui sur lequel il se trouve ;
• s'il existe une possible étape intermédiaire pour effectuer un saut, alors Jøsëf passera par cette étape pour rendre le passage plus sûr.

Vous devez implémenter un algorithme qui calculera le nombre minimum de sauts nécessaires à Jøsëf Marchand pour franchir la rivière.

Il existe toujours un rocher dans le coin en haut à gauche et dans le coin en bas à droite de la rivière.

• La rivière est représentée sous forme d'une grille, avec les 0 représentant de l'eau et les 1 représentant des rochers.
• Jøsëf Marchand doit sauter de rocher en rocher.
• Jøsëf Marchand commence en haut à gauche de la rivière et veut se rendre en bas à droite. Ces deux cases seront toujours des rochers.
• Jøsëf Marchand ne peut pas sauter d'un rocher A vers un rocher B s'il existe un autre rocher dans le rectangle formé par A dans le coin supérieur gauche et B dans le coin inférieur droit.

Par exemple, ce déplacement est impossible :

En revanche, ce déplacement est possible :

L'objectif est de se déplacer du coin supérieur gauche au coin inférieur droit en un minimum de coups.

Entrée¶

L’entrée contiendra :

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

Sortie¶

Afficher le nombre de sauts minimum pour franchir la rivière.

Contraintes¶

• $1 \le hauteur \le 10$
• $1 \le largeur \le 10$
• $riviere[i] \in \{0, 1\}$
• Il ne peut pas y avoir plus de 35 rochers

Contraintes de performance¶

• $1 \le hauteur \le 1\,000$
• $1 \le largeur \le 1\,000$
• Il ne peut pas y avoir plus de 10,000 rochers