Marelle – Épreuve régionale 2012

Niveau 4

É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

Contraintes d'exécution

Utilisation mémoire maximum
5000 kilo-octets
Temps d'exécution maximum
500 millisecondes

Exemples d'entrée/sortie

Exemple d'entrée
5
4
1 0 0 0
1 1 1 1
0 1 0 0
0 2 1 1
1 1 2 1
Exemple de sortie
8
Exemple d'entrée
9
4
1 1 2 1
2 0 0 0
1 1 1 1
1 2 1 1
1 0 0 0
1 1 1 1
0 1 0 0
0 2 1 1
1 1 2 1
Exemple de sortie
13