Marelle – Épreuve régionale 2012

Énoncé¶

Truculent personnage, Joseph Marchand passe sa journée à donner des ordres à ses salariés et à se prélasser, ce qui l'épuise. Ainsi, le soir venu, il se remémore sa jeunesse en particulier ses jeux d'enfance comme les billes, les combats de cartes à jouer Suzumiya Haruhi et la marelle. La marelle du temps de Joseph, celui-ci étant déjà fort âgé, était bien plus compliquée qu'à présent : vous ne pouviez vous déplacer que vers la gauche et vers le haut, et vous ne pouviez marcher que sur les cases cloche-pied (« 1 ») et celles pieds joints (« 2 ») sans déborder sur le reste du terrain (« 0 »). La case terre est la case tout en bas à droite du terrain, la case ciel est celle en haut à gauche.

On vous demande d'écrire une fonction qui retourne le minimum de pieds à poser pour passer de la case terre à la case ciel, en ne se déplaçant que vers la gauche et vers le haut.

On considère que Joseph a déjà posé ses pieds sur la case en bas à droite, c'est pourquoi vous n'avez pas à compter cette case dans votre algorithme. De plus, cette case a toujours pour valeur 1.

On vous garantit également que le chemin pour aller de la case terre à la case ciel existe.

Entrée¶

• Sur la première ligne, la longueur N du terrain ;
• Sur la deuxième ligne, la largeur M du terrain ;
• Sur les lignes suivantes, la disposition de la marelle.

Sortie¶

Le nombre minimum de pieds que vous devez poser pour arriver à la case ciel. Une case "cloche-pied" compte pour 1 pied, un case "pieds joints" pour 2.

Contraintes¶

• 1 <= N, M <= 1 000